Robert E. Tarjan

Affiliations:
  • Princeton University, Department of Computer Science, NJ, USA


According to our database1, Robert E. Tarjan authored at least 292 papers between 1971 and 2023.

Collaborative distances:
  • Dijkstra number2 of two.
  • Erdős number3 of two.

Awards

Turing Prize recipient

Turing Prize 1986, "For fundamental achievements in the design and analysis of algorithms and data structures" awarded to John Hopcroft and Robert Tarjan.

ACM Fellow

ACM Fellow 1994, "For fundamental achievements in the design and analysis of algorithms and data structures.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps.
CoRR, 2023

Efficiency of Self-Adjusting Heaps.
CoRR, 2023

Zip-Zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent.
Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

Optimal resizable arrays.
Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

A Tight Analysis of Slim Heaps and Smooth Heaps.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

A Nearly-Tight Analysis of Multipass Pairing Heaps.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Optimal Energetic Paths for Electric Cars.
Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022
Simple Concurrent Connected Components Algorithms.
ACM Trans. Parallel Comput., 2022

A Simpler Proof that Pairing Heaps Take O(1) Amortized Time per Insertion.
CoRR, 2022

Finding Strong Components Using Depth-First Search.
CoRR, 2022

Simulating a stack using queues.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021
Zip Trees.
ACM Trans. Algorithms, 2021

Concurrent disjoint set union.
Distributed Comput., 2021

An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models.
Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Analysis of Smooth Heaps and Slim Heaps.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020
Connected Components on a PRAM in Log Diameter Time.
Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

2019
New Paths from Splay to Dynamic Optimality.
CoRR, 2019

Splaying Preorders and Postorders.
Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

Simple Concurrent Labeling Algorithms for Connected Components.
Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

A New Path from Splay to Dynamic Optimality.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Randomized Concurrent Set Union and Generalized Wake-Up.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018
Zip Trees.
CoRR, 2018

2017
Hollow Heaps.
ACM Trans. Algorithms, 2017

Minimum-Cost Flows in Unit-Capacity Networks.
Theory Comput. Syst., 2017

2016
Deletion Without Rebalancing in Binary Search Trees.
ACM Trans. Algorithms, 2016

Addendum to "Dominator Tree Certification and Divergent Spanning Trees".
ACM Trans. Algorithms, 2016

Dominator Tree Certification and Divergent Spanning Trees.
ACM Trans. Algorithms, 2016

A New Approach to Incremental Cycle Detection and Related Problems.
ACM Trans. Algorithms, 2016

Amortized rotation cost in AVL trees.
Inf. Process. Lett., 2016

A Randomized Concurrent Algorithm for Disjoint Set Union.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015
Rank-Balanced Trees.
ACM Trans. Algorithms, 2015

A Note on Fault Tolerant Reachability for Directed Graphs.
CoRR, 2015

Minimum Cost Flows in Graphs with Unit Capacities.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search.
Proceedings of the Algorithms - ESA 2015, 2015

2014
Deletion without rebalancing in multiway search trees.
ACM Trans. Database Syst., 2014

Corrections to "Finding dominators via disjoint set union" [J. Discrete Algorithms 23 (2013) 2-20].
J. Discrete Algorithms, 2014

The CB tree: a practical concurrent self-adjusting search tree.
Distributed Comput., 2014

Fibonacci Heaps Revisited.
CoRR, 2014

Efficient maximum flow algorithms.
Commun. ACM, 2014

Loop Nesting Forests, Dominators, and Applications.
Proceedings of the Experimental Algorithms - 13th International Symposium, 2014

Disjoint Set Union with Randomized Linking.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Better Approximation Algorithms for the Graph Diameter.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Nested Set Union.
Proceedings of the Algorithms - ESA 2014, 2014

A Back-to-Basics Empirical Study of Priority Queues.
Proceedings of the 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, 2014

2013
Soft Heaps Simplified.
SIAM J. Comput., 2013

Finding dominators via disjoint set union.
J. Discrete Algorithms, 2013

Dominator Certification and Independent Spanning Trees: An Experimental Study.
Proceedings of the Experimental Algorithms, 12th International Symposium, 2013

2012
Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance.
ACM Trans. Algorithms, 2012

An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries.
SIAM J. Comput., 2012

Dominator Tree Certification and Independent Spanning Trees
CoRR, 2012

CBTree: A Practical Concurrent Self-Adjusting Search Tree.
Proceedings of the Distributed Computing - 26th International Symposium, 2012

Strict fibonacci heaps.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Dominators, Directed Bipolar Orders, and Independent Spanning Trees.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

An Algorithmic View of the Universe.
Proceedings of the ACM Turing Centenary Celebration, 2012

2011
Data structures for mergeable trees.
ACM Trans. Algorithms, 2011

Rank-Pairing Heaps.
SIAM J. Comput., 2011

Theory vs. Practice in the Design and Analysis of Algorithms.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Maximum Flows by Incremental Breadth-First Search.
Proceedings of the Algorithms - ESA 2011, 2011

2010
HP Transforms Product Portfolio Management with Operations Research.
Interfaces, 2010

Deletion Without Rebalancing in Balanced Binary Trees.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Notes on Introductory Combinatorics (reprint of the 1983 edition).
Modern Birkhäuser Classics, Birkhäuser, ISBN: 978-0-8176-4952-4, 2010

2009
Dynamic trees in practice.
ACM J. Exp. Algorithmics, 2009

Shortest-path feasibility algorithms: An experimental evaluation.
ACM J. Exp. Algorithmics, 2009

Heaps Simplified
CoRR, 2009

An Experimental Study of Minimum Mean Cycle Algorithms.
Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009

Efficiently Generating k-Best Solutions to Procurement Auctions.
Proceedings of the Algorithmic Aspects in Information and Management, 2009

2008
Thin heaps, thick heaps.
ACM Trans. Algorithms, 2008

Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems.
SIAM J. Comput., 2008

Finding a feasible flow in a strongly connected network.
Oper. Res. Lett., 2008

Finding Strongly Knit Clusters in Social Networks.
Internet Math., 2008

Planarity Algorithms via PQ-Trees (Extended Abstract).
Electron. Notes Discret. Math., 2008

Incremental Topological Ordering and Strong Component Maintenance
CoRR, 2008

Fast exact and heuristic methods for role minimization problems.
Proceedings of the 13th ACM Symposium on Access Control Models and Technologies, 2008

Reachability Problems on Directed Graphs.
Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

Faster Algorithms for Incremental Topological Ordering.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007
Server Allocation Algorithms for Tiered Systems.
Algorithmica, 2007

Experimental Evaluation of Parametric Max-Flow Algorithms.
Proceedings of the Experimental Algorithms, 6th International Workshop, 2007

Clustering Social Networks.
Proceedings of the Algorithms and Models for the Web-Graph, 5th International Workshop, 2007

2006
Melding priority queues.
ACM Trans. Algorithms, 2006

Finding Dominators in Practice.
J. Graph Algorithms Appl., 2006

Results and Problems on Self-adjusting Search Trees and Related Data Structures.
Proceedings of the Algorithm Theory, 2006

Design of data structures for mergeable trees.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Balancing Applied to Maximum Network Flow Problems.
Proceedings of the Algorithms, 2006

2005
Value-maximizing deadline scheduling and its application to animation rendering.
Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

Self-adjusting top trees.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Dominator tree verification and vertex-disjoint paths.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Deadline scheduling for animation rendering.
Proceedings of the International Conference on Measurements and Modeling of Computer Systems, 2005

2004
Finding dominators revisited: extended abstract.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Finding Dominators in Practice.
Proceedings of the Algorithms, 2004

2003
Graph Clustering and Minimum Cut Trees.
Internet Math., 2003

Dynamic rectangular intersection with priorities.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

If Piracy Is the Problem, Is DRM the Answer?
Proceedings of the Digital Rights Management, 2003

2002
Meldable heaps and boolean union-find.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Union-find with deletions.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001
Unique Maximum Matching Algorithms.
J. Algorithms, 2001

Faster kinetic heaps and their use in broadcast scheduling.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Dynamic Self-Checking Techniques for Improved Tamper Resistance.
Proceedings of the Security and Privacy in Digital Rights Management, 2001

2000
Simple Confluently Persistent Catenable Lists.
SIAM J. Comput., 2000

1999
Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs.
SIAM J. Comput., 1999

A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals.
SIAM J. Comput., 1999

Tight Analyses of Two Local Load Balancing Algorithms.
SIAM J. Comput., 1999

1998
Culturally Induced Information Impactedness: A Prescription for Failure in Software Ventures.
J. Manag. Inf. Syst., 1998

Simple Confluently Persistent Catenable Lists (Extended Abstract).
Proceedings of the Algorithm Theory, 1998

Culturally-Induced Information Impactedness: A Prescription for Failure in Software Ventures.
Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences, 1998

Robustness and Security of Digital Watermarks.
Proceedings of the Financial Cryptography, 1998

1997
Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm.
Math. Program., 1997

Toward Efficient Unstructured Multigrid Preprocessing.
Int. J. High Perform. Comput. Appl., 1997

Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time.
Algorithmica, 1997

1996
Analysis of Multigrid Algorithms on Massively Parallel Computers: Architectural Implications.
J. Parallel Distributed Comput., 1996

Parallelism in multigrid methods: How much is too much?
Int. J. Parallel Program., 1996

Dominating Sets in Planar Graphs.
Eur. J. Comb., 1996

Purely Functional Representations of Catenable Sorted Lists.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling.
Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996

Toward Efficient Unstructured Multigrid Preprocessing (Extended Abstract).
Proceedings of the Parallel Algorithms for Irregularly Structured Problems, 1996

1995
Computing Minimal Spanning Subgraphs in Linear Time.
SIAM J. Comput., 1995

Data-Structural Bootstrapping, Linear Path Compression, and Catenable Heap-Ordered Double-Ended Queues.
SIAM J. Comput., 1995

Confluently Persistent Deques via Data-Structural Bootstrapping.
J. Algorithms, 1995

A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.
J. ACM, 1995

Lazy Structure Sharing for Query Optimization.
Acta Informatica, 1995

Persistent lists with catenation via recursive slow-down.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Models of parallel computation: a survey and synthesis.
Proceedings of the 28th Annual Hawaii International Conference on System Sciences (HICSS-28), 1995

1994
Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences.
SIAM J. Comput., 1994

Dynamic Perfect Hashing: Upper and Lower Bounds.
SIAM J. Comput., 1994

Improved Algorithms for Bipartite Network Flow.
SIAM J. Comput., 1994

A Faster Deterministic Maximum Flow Algorithm.
J. Algorithms, 1994

Fully Persistent Lists with Catenation.
J. ACM, 1994

A randomized linear-time algorithm for finding minimum spanning trees.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Unstructured Multigrid Strategies on Massively Parallel Computers: A Case for Integrated Design.
Proceedings of the 27th Annual Hawaii International Conference on System Sciences (HICSS-27), 1994

Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
An O(m log n)-Time Algorithm for the Maximal Planar Subgraph Problem.
SIAM J. Comput., 1993

Corrigendum: Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph.
J. Algorithms, 1993

Finding the Minimum-Cost Maximum Flow in a Series-Parallel Network.
J. Algorithms, 1993

1992
More Efficient Bottom-Up Multi-Pattern Matching in Trees.
Theor. Comput. Sci., 1992

Short Encodings of Evolving Structures.
SIAM J. Discret. Math., 1992

Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time.
SIAM J. Comput., 1992

Finding minimum-cost flows by double scaling.
Math. Program., 1992

Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph.
J. Algorithms, 1992

Erratum: Randomized parallel algorithms for trapezoidal diagrams.
Int. J. Comput. Geom. Appl., 1992

Randomized parallel algorithms for trapezoidal diagrams.
Int. J. Comput. Geom. Appl., 1992

Polygon Triangulation in O (n log log n) Time with Simple Data Structures.
Discret. Comput. Geom., 1992

Maintaining Bridge-Connected and Biconnected Components On-Line.
Algorithmica, 1992

A Linear-Time Algorithm for Finding an Ambitus.
Algorithmica, 1992

1991
Faster parametric shortest path and minimum-balance algorithms.
Networks, 1991

Use of dynamic trees in a network simplex algorithm for the maximum flow problem.
Math. Program., 1991

Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem.
Math. Oper. Res., 1991

Transitive Compaction in Parallel via Branchings.
J. Algorithms, 1991

Faster Scaling Algorithms for General Graph-Matching Problems.
J. ACM, 1991

1990
Faster Algorithms for the Shortest Path Problem
J. ACM, April, 1990

Finding Minimum-Cost Circulations by Successive Approximation.
Math. Oper. Res., 1990

Simplified Linear-Time Jordan Sorting and Polygon Clipping.
Inf. Process. Lett., 1990

Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

More Efficient Bottom-Up Tree Pattern Matching.
Proceedings of the CAAP '90, 1990

1989
Amortized Analysis of Algorithms for Set Union with Backtracking.
SIAM J. Comput., 1989

A Fast Parametric Maximum Flow Algorithm and Applications.
SIAM J. Comput., 1989

Faster Scaling Algorithms for Network Problems.
SIAM J. Comput., 1989

Improved Time Bounds for the Maximum Flow Problem.
SIAM J. Comput., 1989

Making Data Structures Persistent.
J. Comput. Syst. Sci., 1989

Finding minimum-cost circulations by canceling negative cycles.
J. ACM, 1989

A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network.
Inf. Process. Lett., 1989

A Tight Amortized Bound for Path Reversal.
Inf. Process. Lett., 1989

A Fast Las Vegas Algorithm for Triangulating a Simple Polygon.
Discret. Comput. Geom., 1989

1988
Erratum: An O(n log log n)-Time Algorithm for Triangulating a Simple Polygon.
SIAM J. Comput., 1988

An O(n log log n)-Time Algorithm for Triangulating a Simple Polygon.
SIAM J. Comput., 1988

One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties.
Math. Oper. Res., 1988

Algorithms for Two Bottleneck Optimization Problems.
J. Algorithms, 1988

A new approach to the maximum-flow problem.
J. ACM, 1988

A Linear-Time Algorithm for Finding a Minimum Spanning Pseudoforest.
Inf. Process. Lett., 1988

Relaxed Heaps: An Alternative to Fibonacci Heaps with Applications to Parallel Computation.
Commun. ACM, 1988

Almost-Optimum Speed-ups of Algorithms for Bipartite Matching and Related Problems
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1987
Three Partition Refinement Algorithms.
SIAM J. Comput., 1987

Fibonacci heaps and their uses in improved network optimization algorithms.
J. ACM, 1987

Algorithmic Design.
Commun. ACM, 1987

Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons.
Algorithmica, 1987

Solving Minimum-Cost Flow Problems by Successive Approximation
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Correction to "A Linear-Time Algorithm for Triangulating Simple Polygons"
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986
Self-Adjusting Heaps.
SIAM J. Comput., 1986

Deques with Heap Order.
Inf. Process. Lett., 1986

Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees
Inf. Control., 1986

Rectilinear Planar Layouts and Bipolar Orientations of Planar Graphs.
Discret. Comput. Geom., 1986

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs.
Comb., 1986

Planar Point Location Using Persistent Search Trees.
Commun. ACM, 1986

A Locally Adaptive Data Compression Scheme.
Commun. ACM, 1986

The Pairing Heap: A New Form of Self-Adjusting Heap.
Algorithmica, 1986

A Linear-Time Algorithm for Triangulating Simple Polygons
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Rotation Distance, Triangulations, and Hyperbolic Geometry
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Linear Time Algorithms for Visibility and Shortest Path Problems Inside Simple Polygons.
Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

1985
Self-Adjusting Binary Search Trees
J. ACM, July, 1985

A Linear Time Solution to the Single Function Coarsest Partition Problem.
Theor. Comput. Sci., 1985

Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs.
SIAM J. Comput., 1985

An Efficient Parallel Biconnectivity Algorithm.
SIAM J. Comput., 1985

Biased Search Trees.
SIAM J. Comput., 1985

Strongly connected orientations of mixed multigraphs.
Networks, 1985

A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees.
Math. Oper. Res., 1985

A Linear-Time Algorithm for a Special Case of Disjoint Set Union.
J. Comput. Syst. Sci., 1985

Decomposition by clique separators.
Discret. Math., 1985

Sequential access in play trees takes linear time.
Comb., 1985

Amortized Efficiency of List Update and Paging Rules.
Commun. ACM, 1985

Sorting Jordan sequences in linear time.
Proceedings of the First Annual Symposium on Computational Geometry, 1985

1984
Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs.
SIAM J. Comput., 1984

Fast Algorithms for Finding Nearest Common Ancestors.
SIAM J. Comput., 1984

A quick method for finding shortest pairs of disjoint paths.
Networks, 1984

Gauss Codes, Planar Hamiltonian Graphs, and Stack-Sortable Permutations.
J. Algorithms, 1984

A Separator Theorem for Graphs of Bounded Genus.
J. Algorithms, 1984

Efficient Algorithms for a Family of Matroid Intersection Problems.
J. Algorithms, 1984

Worst-case Analysis of Set Union Algorithms.
J. ACM, 1984

Amortized Efficiency of List Update Rules
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Scaling and Related Techniques for Geometry Problems
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

A Linear Time Algorithm to Solve the Single Function Coarsest Partition Problem.
Proceedings of the Automata, 1984

Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Space-Efficient Implementations of Graph Search Methods.
ACM Trans. Math. Softw., 1983

A Data Structure for Dynamic Trees.
J. Comput. Syst. Sci., 1983

An Improved Algorithm for Hierarchical Clustering Using Strong Components.
Inf. Process. Lett., 1983

Updating a Balanced Search Tree in O(1) Rotations.
Inf. Process. Lett., 1983

Two new kinds of biased search trees.
Bell Syst. Tech. J., 1983

Self-Adjusting Binary Trees
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Notes on introductory combinatorics.
Progress in computer science 4, Birkhäuser, ISBN: 978-3-7643-3170-2, 1983

Data structures and network algorithms.
CBMS-NSF regional conference series in applied mathematics 44, SIAM, ISBN: 978-1-61197-026-5, 1983

1982
The Recognition of Series Parallel Digraphs.
SIAM J. Comput., 1982

Symbolic Program Analysis in Almost-Linear Time.
SIAM J. Comput., 1982

Asymptotically tight bounds on time-space trade-offs in a pebble game.
J. ACM, 1982

Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees.
Inf. Process. Lett., 1982

A Hierarchical Clustering Algorithm Using Strong Components.
Inf. Process. Lett., 1982

1981
On a Greedy Heuristic for Complete Matching.
SIAM J. Comput., 1981

Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines.
SIAM J. Comput., 1981

Fast Algorithms for Solving Path Problems.
J. ACM, 1981

A Unified Approach to Path Problems.
J. ACM, 1981

1980
Applications of a Planar Separator Theorem.
SIAM J. Comput., 1980

The Pebbling Problem is Complete in Polynomial Space.
SIAM J. Comput., 1980

Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms.
SIAM J. Comput., 1980

Design and Analysis of a Data Structure for Representing Sorted Lists.
SIAM J. Comput., 1980

Linear Expected-Time Algorithms for Connectivity Problems.
J. Algorithms, 1980

Variations on the Common Subexpression Problem.
J. ACM, 1980

The Space Complexity of Pebble Games on Trees.
Inf. Process. Lett., 1980

Linear Expected-Time Algorithms for Connectivity Problems (Extended Abstract)
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

Prime Subprogram Parsing of a Program.
Proceedings of the Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, 1980

Biased 2-3 Trees
Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980

1979
A Fast Algorithm for Finding Dominators in a Flowgraph.
ACM Trans. Program. Lang. Syst., 1979

A Class of Algorithms which Require Nonlinear Time to Maintain Disjoint Sets.
J. Comput. Syst. Sci., 1979

Applications of Path Compression on Balanced Trees.
J. ACM, 1979

A Fast Merging Algorithm.
J. ACM, 1979

A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas.
Inf. Process. Lett., 1979

Storing a Sparse Table.
Commun. ACM, 1979

Upper and Lower Bounds on Time-Space Tradeoffs
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

Efficient Algorithms for Simple Matroid Intersection Problems
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
A Linear-Time Algorithm for Finding All Feedback Vertices.
Inf. Process. Lett., 1978

Triangulating a Simple Polygon.
Inf. Process. Lett., 1978

Time-Space Trade-Offs in a Pebble Game.
Acta Informatica, 1978

A Representation for Linear Lists with Movable Fingers
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

1977
Corrigendum: Computing an <i>st</i>-Numbering. TCS 2(1976):339-344.
Theor. Comput. Sci., 1977

Finding a Maximum Independent Set.
SIAM J. Comput., 1977

Finding optimum branchings.
Networks, 1977

Correction: Space Bounds for a Game on Graphs.
Math. Syst. Theory, 1977

Space Bounds for a Game on Graphs.
Math. Syst. Theory, 1977

Reference Machines Require Non-linear Time to Maintain Disjoint Sets
Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977

Application of a Planar Separator Theorem
Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977

1976
Computing an <i> st </i> -Numbering.
Theor. Comput. Sci., 1976

Algorithmic Aspects of Vertex Elimination on Graphs.
SIAM J. Comput., 1976

b-Matchings in Trees.
SIAM J. Comput., 1976

The Planar Hamiltonian Circuit Problem is NP-Complete.
SIAM J. Comput., 1976

Augmentation Problems.
SIAM J. Comput., 1976

Finding Minimum Spanning Trees.
SIAM J. Comput., 1976

Intersection graphs of curves in the plane.
J. Comb. Theory, Ser. B, 1976

A Combinatorial Problem Which Is Complete in Polynomial Space.
J. ACM, 1976

Lower bounds on the lengths of node sequences in directed graphs.
Discret. Math., 1976

Edge-Disjoint Spanning Trees and Depth-First Search.
Acta Informatica, 1976

1975
Network Flow and Testing Graph Connectivity.
SIAM J. Comput., 1975

Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees.
Networks, 1975

Efficiency of a Good But Not Linear Set Union Algorithm.
J. ACM, 1975

Optimal Chain Partitions of Trees.
Inf. Process. Lett., 1975

Algorithmic Aspects of Vertex Elimination
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

1974
Finding Dominators in Directed Graphs.
SIAM J. Comput., 1974

Testing Flow Graph Reducibility.
J. Comput. Syst. Sci., 1974

Efficient Planarity Testing.
J. ACM, 1974

A Good Algorithm for Edge-Disjoint Branching.
Inf. Process. Lett., 1974

A New Algorithm for Finding Weak Components.
Inf. Process. Lett., 1974

A Note on Finding the Bridges of a Graph.
Inf. Process. Lett., 1974

Testing Graph Connectivity
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1973
Enumeration of the Elementary Circuits of a Directed Graph.
SIAM J. Comput., 1973

Dividing a Graph into Triconnected Components.
SIAM J. Comput., 1973

A V log V Algorithm for Isomorphism of Triconnected Planar Graphs.
J. Comput. Syst. Sci., 1973

Time Bounds for Selection.
J. Comput. Syst. Sci., 1973

Efficient Algorithms for Graph Manipulation [H] (Algorithm 447).
Commun. ACM, 1973

1972
Depth-First Search and Linear Graph Algorithms.
SIAM J. Comput., 1972

Sorting Using Networks of Queues and Stacks.
J. ACM, 1972

Determining Whether a Groupoid is a Group.
Inf. Process. Lett., 1972

Linear Time Bounds for Median Computations
Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972

Isomorphism of Planar Graphs.
Proceedings of a symposium on the Complexity of Computer Computations, 1972

1971
An efficient planarity algorithm.
PhD thesis, 1971

A V² Algorithm for Determining Isomorphism of Planar Graphs.
Inf. Process. Lett., 1971

Planarity Testing in <i>V</i> log <i>V</i> Steps: Extended Abstract.
Proceedings of the Information Processing, Proceedings of IFIP Congress 1971, Volume 1, 1971

Depth-First Search and Linear Graph Algorithms (Working Paper)
Proceedings of the 12th Annual Symposium on Switching and Automata Theory, 1971


  Loading...