Robert E. Tarjan

SIAM J. Comput., 2024

Finding strong components using depth-first search.

[BibT_eX]

[DOI]

Eur. J. Comb., 2024

Fast and Simple Sorting Using Partial Information.

[BibT_eX]

[DOI]

CoRR, 2024

Minimum-cost paths for electric cars.

[BibT_eX]

[DOI]

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Fast, Scalable, and Machine-Verified Multicore Disjoint Set Union Data Structures and their Wide Deployment in Parallel Algorithms (Abstract).

[BibT_eX]

[DOI]

Siddhartha Jayanti

Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing, 2024

2023

Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps.

[BibT_eX]

[DOI]

CoRR, 2023

Efficiency of Self-Adjusting Heaps.

[BibT_eX]

[DOI]

CoRR, 2023

Zip-Zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent.

[BibT_eX]

[DOI]

Ofek Gila

Michael T. Goodrich

Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

A Tight Analysis of Slim Heaps and Smooth Heaps.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

A Nearly-Tight Analysis of Multipass Pairing Heaps.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Optimal Energetic Paths for Electric Cars.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Simple Concurrent Connected Components Algorithms.

[BibT_eX]

[DOI]

Sixue Cliff Liu

ACM Trans. Parallel Comput., 2022

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

[BibT_eX]

[DOI]

CoRR, 2022

Simulating a stack using queues.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021

Zip Trees.

[BibT_eX]

[DOI]

Stephen Timmel

ACM Trans. Algorithms, 2021

Concurrent disjoint set union.

[BibT_eX]

[DOI]

Siddhartha V. Jayanti

Distributed Comput., 2021

An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models.

[BibT_eX]

[DOI]

Sepehr Assadi

S. Cliff Liu

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Analysis of Smooth Heaps and Slim Heaps.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Connected Components on a PRAM in Log Diameter Time.

[BibT_eX]

[DOI]

Sixue Cliff Liu

Peilin Zhong

Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

2019

New Paths from Splay to Dynamic Optimality.

[BibT_eX]

[DOI]

CoRR, 2019

Splaying Preorders and Postorders.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

Simple Concurrent Labeling Algorithms for Connected Components.

[BibT_eX]

[DOI]

Sixue Liu

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

A New Path from Splay to Dynamic Optimality.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Randomized Concurrent Set Union and Generalized Wake-Up.

[BibT_eX]

[DOI]

Siddhartha V. Jayanti

Enric Boix-Adserà

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018

Zip Trees.

[BibT_eX]

[DOI]

CoRR, 2018

2017

Hollow Heaps.

[BibT_eX]

[DOI]

Thomas Dueholm Hansen

ACM Trans. Algorithms, 2017

Minimum-Cost Flows in Unit-Capacity Networks.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

2016

Deletion Without Rebalancing in Binary Search Trees.

[BibT_eX]

[DOI]

David Hong Kyun Kim

ACM Trans. Algorithms, 2016

Addendum to "Dominator Tree Certification and Divergent Spanning Trees".

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Dominator Tree Certification and Divergent Spanning Trees.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

A New Approach to Incremental Cycle Detection and Related Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Amortized rotation cost in AVL trees.

[BibT_eX]

[DOI]

Mahdi Amani

Kevin A. Lai

Inf. Process. Lett., 2016

A Randomized Concurrent Algorithm for Disjoint Set Union.

[BibT_eX]

[DOI]

Siddhartha V. Jayanti

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015

Rank-Balanced Trees.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2015

A Note on Fault Tolerant Reachability for Directed Graphs.

[BibT_eX]

[DOI]

CoRR, 2015

Minimum Cost Flows in Graphs with Unit Capacities.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

2014

Deletion without rebalancing in multiway search trees.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2014

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

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2014

The CB tree: a practical concurrent self-adjusting search tree.

[BibT_eX]

[DOI]

Distributed Comput., 2014

Fibonacci Heaps Revisited.

[BibT_eX]

[DOI]

CoRR, 2014

Efficient maximum flow algorithms.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Commun. ACM, 2014

Loop Nesting Forests, Dominators, and Applications.

[BibT_eX]

[DOI]

Proceedings of the Experimental Algorithms - 13th International Symposium, 2014

Disjoint Set Union with Randomized Linking.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Better Approximation Algorithms for the Graph Diameter.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Nested Set Union.

[BibT_eX]

[DOI]

Daniel H. Larkin

Proceedings of the Algorithms - ESA 2014, 2014

A Back-to-Basics Empirical Study of Priority Queues.

[BibT_eX]

[DOI]

Daniel H. Larkin

Proceedings of the 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, 2014

2013

Soft Heaps Simplified.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Finding dominators via disjoint set union.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2013

Dominator Certification and Independent Spanning Trees: An Experimental Study.

[BibT_eX]

[DOI]

Proceedings of the Experimental Algorithms, 12th International Symposium, 2013

2012

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Dominator Tree Certification and Independent Spanning Trees

[BibT_eX]

[DOI]

CoRR, 2012

CBTree: A Practical Concurrent Self-Adjusting Search Tree.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 26th International Symposium, 2012

Strict fibonacci heaps.

[BibT_eX]

[DOI]

Gerth Stølting Brodal

George Lagogiannis

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Dominators, Directed Bipolar Orders, and Independent Spanning Trees.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs.

[BibT_eX]

[DOI]

Lyle Ramshaw

Christos H. Papadimitriou

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

An Algorithmic View of the Universe.

[BibT_eX]

[DOI]

Proceedings of the ACM Turing Centenary Celebration, 2012

2011

Data structures for mergeable trees.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2011

Rank-Pairing Heaps.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Theory vs. Practice in the Design and Analysis of Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Maximum Flows by Incremental Breadth-First Search.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2011, 2011

2010

HP Transforms Product Portfolio Management with Operations Research.

[BibT_eX]

[DOI]

Interfaces, 2010

Deletion Without Rebalancing in Balanced Binary Trees.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Notes on Introductory Combinatorics (reprint of the 1983 edition).

[BibT_eX]

George Pólya

Donald R. Woods

Modern Birkhäuser Classics, Birkhäuser, ISBN: 978-0-8176-4952-4, 2010

2009

Dynamic trees in practice.

[BibT_eX]

[DOI]

ACM J. Exp. Algorithmics, 2009

Shortest-path feasibility algorithms: An experimental evaluation.

[BibT_eX]

[DOI]

ACM J. Exp. Algorithmics, 2009

Heaps Simplified

[BibT_eX]

[DOI]

CoRR, 2009

An Experimental Study of Minimum Mean Cycle Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009

Efficiently Generating k-Best Solutions to Procurement Auctions.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects in Information and Management, 2009

2008

Thin heaps, thick heaps.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2008

Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Finding a feasible flow in a strongly connected network.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2008

Finding Strongly Knit Clusters in Social Networks.

[BibT_eX]

[DOI]

Internet Math., 2008

Planarity Algorithms via PQ-Trees (Extended Abstract).

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2008

Incremental Topological Ordering and Strong Component Maintenance

[BibT_eX]

[DOI]

CoRR, 2008

Fast exact and heuristic methods for role minimization problems.

[BibT_eX]

[DOI]

Proceedings of the 13th ACM Symposium on Access Control Models and Technologies, 2008

Reachability Problems on Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

Faster Algorithms for Incremental Topological Ordering.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Server Allocation Algorithms for Tiered Systems.

[BibT_eX]

[DOI]

Algorithmica, 2007

Experimental Evaluation of Parametric Max-Flow Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Experimental Algorithms, 6th International Workshop, 2007

Clustering Social Networks.

[BibT_eX]

[DOI]

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

2006

Melding priority queues.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2006

Finding Dominators in Practice.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2006

Results and Problems on Self-adjusting Search Trees and Related Data Structures.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2006

Design of data structures for mergeable trees.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Balancing Applied to Maximum Network Flow Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2006

2005

Value-maximizing deadline scheduling and its application to animation rendering.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

Self-adjusting top trees.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Dominator tree verification and vertex-disjoint paths.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Deadline scheduling for animation rendering.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Measurements and Modeling of Computer Systems, 2005

2004

Finding dominators revisited: extended abstract.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Finding Dominators in Practice.

[BibT_eX]

[DOI]

Spyridon Triantafyllis

David I. August

Proceedings of the Algorithms, 2004

2003

Graph Clustering and Minimum Cut Trees.

[BibT_eX]

[DOI]

Gary William Flake

Kostas Tsioutsiouliklis

Internet Math., 2003

Dynamic rectangular intersection with priorities.

[BibT_eX]

[DOI]

Eyal Molad

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

If Piracy Is the Problem, Is DRM the Answer?

[BibT_eX]

[DOI]

Proceedings of the Digital Rights Management, 2003

2002

Meldable heaps and boolean union-find.

[BibT_eX]

[DOI]

Nira Shafrir

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Union-find with deletions.

[BibT_eX]

[DOI]

Nira Shafrir

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001

Unique Maximum Matching Algorithms.

[BibT_eX]

[DOI]

J. Algorithms, 2001

Faster kinetic heaps and their use in broadcast scheduling.

[BibT_eX]

[DOI]

Kostas Tsioutsiouliklis

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Dynamic Self-Checking Techniques for Improved Tamper Resistance.

[BibT_eX]

[DOI]

Proceedings of the Security and Privacy in Digital Rights Management, 2001

2000

Simple Confluently Persistent Catenable Lists.

[BibT_eX]

[DOI]

Chris Okasaki

SIAM J. Comput., 2000

1999

Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs.

[BibT_eX]

[DOI]

Ron Shamir

SIAM J. Comput., 1999

A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals.

[BibT_eX]

[DOI]

Ron Shamir

SIAM J. Comput., 1999

Tight Analyses of Two Local Load Balancing Algorithms.

[BibT_eX]

[DOI]

Bhaskar Ghosh

Frank Thomson Leighton

SIAM J. Comput., 1999

1998

Culturally Induced Information Impactedness: A Prescription for Failure in Software Ventures.

[BibT_eX]

[DOI]

J. Manag. Inf. Syst., 1998

Simple Confluently Persistent Catenable Lists (Extended Abstract).

[BibT_eX]

[DOI]

Chris Okasaki

Proceedings of the Algorithm Theory, 1998

Culturally-Induced Information Impactedness: A Prescription for Failure in Software Ventures.

[BibT_eX]

[DOI]

Talal Shamoon

Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences, 1998

Robustness and Security of Digital Watermarks.

[BibT_eX]

[DOI]

Proceedings of the Financial Cryptography, 1998

1997

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

[BibT_eX]

[DOI]

Math. Program., 1997

Toward Efficient Unstructured Multigrid Preprocessing.

[BibT_eX]

[DOI]

Susan E. Dorward

Int. J. High Perform. Comput. Appl., 1997

Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time.

[BibT_eX]

[DOI]

Brandon Dixon

Algorithmica, 1997

1996

Analysis of Multigrid Algorithms on Massively Parallel Computers: Architectural Implications.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 1996

Parallelism in multigrid methods: How much is too much?

[BibT_eX]

[DOI]

Int. J. Parallel Program., 1996

Dominating Sets in Planar Graphs.

[BibT_eX]

[DOI]

Eur. J. Comb., 1996

Purely Functional Representations of Catenable Sorted Lists.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Richard Cole

Philip N. Klein

Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996

Toward Efficient Unstructured Multigrid Preprocessing (Extended Abstract).

[BibT_eX]

[DOI]

Susan E. Dorward

Proceedings of the Parallel Algorithms for Irregularly Structured Problems, 1996

1995

Computing Minimal Spanning Subgraphs in Linear Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 1995

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

[BibT_eX]

[DOI]

Adam L. Buchsbaum

Rajamani Sundar

SIAM J. Comput., 1995

Confluently Persistent Deques via Data-Structural Bootstrapping.

[BibT_eX]

[DOI]

Adam L. Buchsbaum

J. Algorithms, 1995

A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.

[BibT_eX]

[DOI]

David R. Karger

Philip N. Klein

J. ACM, 1995

Lazy Structure Sharing for Query Optimization.

[BibT_eX]

[DOI]

Adam L. Buchsbaum

Rajamani Sundar

Acta Informatica, 1995

Persistent lists with catenation via recursive slow-down.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Models of parallel computation: a survey and synthesis.

[BibT_eX]

[DOI]

Bruce M. Maggs

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.

[BibT_eX]

[DOI]

Rajamani Sundar

Friedhelm Meyer auf der Heide

SIAM J. Comput., 1994

Dynamic Perfect Hashing: Upper and Lower Bounds.

[BibT_eX]

[DOI]

Martin Dietzfelbinger

Anna R. Karlin

Kurt Mehlhorn

Hans Rohnert

SIAM J. Comput., 1994

Improved Algorithms for Bipartite Network Flow.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

A Faster Deterministic Maximum Flow Algorithm.

[BibT_eX]

[DOI]

Valerie King

S. Rao

J. Algorithms, 1994

Fully Persistent Lists with Catenation.

[BibT_eX]

[DOI]

James R. Driscoll

J. ACM, 1994

A randomized linear-time algorithm for finding minimum spanning trees.

[BibT_eX]

[DOI]

Philip N. Klein

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.

[BibT_eX]

Susan E. Dorward

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

[BibT_eX]

[DOI]

Ron Shamir

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.

[BibT_eX]

[DOI]

Jiazhen Cai

Xiaofeng Han

SIAM J. Comput., 1993

Corrigendum: Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph.

[BibT_eX]

J. Algorithms, 1993

Finding the Minimum-Cost Maximum Flow in a Series-Parallel Network.

[BibT_eX]

[DOI]

Heather Booth

J. Algorithms, 1993

1992

More Efficient Bottom-Up Multi-Pattern Matching in Trees.

[BibT_eX]

[DOI]

Jiazhen Cai

Theor. Comput. Sci., 1992

Short Encodings of Evolving Structures.

[BibT_eX]

[DOI]

William P. Thurston

SIAM J. Discret. Math., 1992

Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time.

[BibT_eX]

[DOI]

Brandon Dixon

Monika Rauch

SIAM J. Comput., 1992

Finding minimum-cost flows by double scaling.

[BibT_eX]

[DOI]

Math. Program., 1992

Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph.

[BibT_eX]

[DOI]

J. Algorithms, 1992

Erratum: Randomized parallel algorithms for trapezoidal diagrams.

[BibT_eX]

[DOI]

Kenneth L. Clarkson

Richard Cole

Int. J. Comput. Geom. Appl., 1992

Randomized parallel algorithms for trapezoidal diagrams.

[BibT_eX]

[DOI]

Kenneth L. Clarkson

Richard Cole

Int. J. Comput. Geom. Appl., 1992

Polygon Triangulation in O (n log log n) Time with Simple Data Structures.

[BibT_eX]

[DOI]

David G. Kirkpatrick

Maria M. Klawe

Discret. Comput. Geom., 1992

Maintaining Bridge-Connected and Biconnected Components On-Line.

[BibT_eX]

[DOI]

Jeffery R. Westbrook

Algorithmica, 1992

A Linear-Time Algorithm for Finding an Ambitus.

[BibT_eX]

[DOI]

Bhubaneswar Mishra

Algorithmica, 1992

1991

Faster parametric shortest path and minimum-balance algorithms.

[BibT_eX]

[DOI]

Neal E. Young

James B. Orlin

Networks, 1991

Use of dynamic trees in a network simplex algorithm for the maximum flow problem.

[BibT_eX]

[DOI]

Michael D. Grigoriadis

Math. Program., 1991

Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem.

[BibT_eX]

[DOI]

Math. Oper. Res., 1991

Transitive Compaction in Parallel via Branchings.

[BibT_eX]

[DOI]

J. Algorithms, 1991

Faster Scaling Algorithms for General Graph-Matching Problems.

[BibT_eX]

[DOI]

J. ACM, 1991

1990

Faster Algorithms for the Shortest Path Problem

[BibT_eX]

[DOI]

J. ACM, April, 1990

Finding Minimum-Cost Circulations by Successive Approximation.

[BibT_eX]

[DOI]

Math. Oper. Res., 1990

Simplified Linear-Time Jordan Sorting and Polygon Clipping.

[BibT_eX]

[DOI]

Khun Yee Fung

Tina M. Nicholl

Inf. Process. Lett., 1990

Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph.

[BibT_eX]

[DOI]

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

More Efficient Bottom-Up Tree Pattern Matching.

[BibT_eX]

[DOI]

Jiazhen Cai

Proceedings of the CAAP '90, 1990

1989

Amortized Analysis of Algorithms for Set Union with Backtracking.

[BibT_eX]

[DOI]

Jeffery R. Westbrook

SIAM J. Comput., 1989

A Fast Parametric Maximum Flow Algorithm and Applications.

[BibT_eX]

[DOI]

Giorgio Gallo

Michael D. Grigoriadis

SIAM J. Comput., 1989

Faster Scaling Algorithms for Network Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

Improved Time Bounds for the Maximum Flow Problem.

[BibT_eX]

[DOI]

Ravindra K. Ahuja

James B. Orlin

SIAM J. Comput., 1989

Making Data Structures Persistent.

[BibT_eX]

[DOI]

James R. Driscoll

Neil Sarnak

J. Comput. Syst. Sci., 1989

Finding minimum-cost circulations by canceling negative cycles.

[BibT_eX]

[DOI]

J. ACM, 1989

A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1989

A Tight Amortized Bound for Path Reversal.

[BibT_eX]

[DOI]

David Ginat

Inf. Process. Lett., 1989

A Fast Las Vegas Algorithm for Triangulating a Simple Polygon.

[BibT_eX]

[DOI]

Kenneth L. Clarkson

Discret. Comput. Geom., 1989

1988

Erratum: An O(n log log n)-Time Algorithm for Triangulating a Simple Polygon.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

An O(n log log n)-Time Algorithm for Triangulating a Simple Polygon.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties.

[BibT_eX]

[DOI]

Michael R. Garey

Gordon T. Wilfong

Math. Oper. Res., 1988

Algorithms for Two Bottleneck Optimization Problems.

[BibT_eX]

[DOI]

J. Algorithms, 1988

A new approach to the maximum-flow problem.

[BibT_eX]

[DOI]

J. ACM, 1988

A Linear-Time Algorithm for Finding a Minimum Spanning Pseudoforest.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1988

Relaxed Heaps: An Alternative to Fibonacci Heaps with Applications to Parallel Computation.

[BibT_eX]

[DOI]

Commun. ACM, 1988

Almost-Optimum Speed-ups of Algorithms for Bipartite Matching and Related Problems

[BibT_eX]

[DOI]

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1987

Three Partition Refinement Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 1987

Fibonacci heaps and their uses in improved network optimization algorithms.

[BibT_eX]

[DOI]

Michael L. Fredman

J. ACM, 1987

Algorithmic Design.

[BibT_eX]

[DOI]

Commun. ACM, 1987

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

[BibT_eX]

[DOI]

Algorithmica, 1987

Solving Minimum-Cost Flow Problems by Successive Approximation

[BibT_eX]

[DOI]

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Correction to "A Linear-Time Algorithm for Triangulating Simple Polygons"

[BibT_eX]

[DOI]

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986

Self-Adjusting Heaps.

[BibT_eX]

[DOI]

SIAM J. Comput., 1986

Deques with Heap Order.

[BibT_eX]

[DOI]

H. Gajewska

Inf. Process. Lett., 1986

Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees

[BibT_eX]

[DOI]

Inf. Control., 1986

Rectilinear Planar Layouts and Bipolar Orientations of Planar Graphs.

[BibT_eX]

[DOI]

Pierre Rosenstiehl

Discret. Comput. Geom., 1986

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

[BibT_eX]

[DOI]

Comb., 1986

Planar Point Location Using Persistent Search Trees.

[BibT_eX]

[DOI]

Neil Sarnak

Commun. ACM, 1986

A Locally Adaptive Data Compression Scheme.

[BibT_eX]

[DOI]

Jon Louis Bentley

Victor K. Wei

Commun. ACM, 1986

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

[BibT_eX]

[DOI]

Michael L. Fredman

Robert Sedgewick

Algorithmica, 1986

A Linear-Time Algorithm for Triangulating Simple Polygons

[BibT_eX]

[DOI]

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Rotation Distance, Triangulations, and Hyperbolic Geometry

[BibT_eX]

[DOI]

William P. Thurston

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Linear Time Algorithms for Visibility and Shortest Path Problems Inside Simple Polygons.

[BibT_eX]

[DOI]

Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

1985

Self-Adjusting Binary Search Trees

[BibT_eX]

[DOI]

J. ACM, July, 1985

A Linear Time Solution to the Single Function Coarsest Partition Problem.

[BibT_eX]

[DOI]

Robert Bonic

Theor. Comput. Sci., 1985

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

[BibT_eX]

[DOI]

Mihalis Yannakakis

SIAM J. Comput., 1985

An Efficient Parallel Biconnectivity Algorithm.

[BibT_eX]

[DOI]

Uzi Vishkin

SIAM J. Comput., 1985

Biased Search Trees.

[BibT_eX]

[DOI]

Samuel W. Bent

SIAM J. Comput., 1985

Strongly connected orientations of mixed multigraphs.

[BibT_eX]

[DOI]

Fan R. K. Chung

Michael R. Garey

Networks, 1985

A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees.

[BibT_eX]

[DOI]

James Roskind

Math. Oper. Res., 1985

A Linear-Time Algorithm for a Special Case of Disjoint Set Union.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1985

Decomposition by clique separators.

[BibT_eX]

[DOI]

Discret. Math., 1985

Sequential access in play trees takes linear time.

[BibT_eX]

[DOI]

Comb., 1985

Amortized Efficiency of List Update and Paging Rules.

[BibT_eX]

[DOI]

Commun. ACM, 1985

Sorting Jordan sequences in linear time.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Mihalis Yannakakis

SIAM J. Comput., 1984

Fast Algorithms for Finding Nearest Common Ancestors.

[BibT_eX]

[DOI]

Dov Harel

SIAM J. Comput., 1984

A quick method for finding shortest pairs of disjoint paths.

[BibT_eX]

[DOI]

J. W. Suurballe

Networks, 1984

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

[BibT_eX]

[DOI]

Pierre Rosenstiehl

J. Algorithms, 1984

A Separator Theorem for Graphs of Bounded Genus.

[BibT_eX]

[DOI]

John R. Gilbert

Joan P. Hutchinson

J. Algorithms, 1984

Efficient Algorithms for a Family of Matroid Intersection Problems.

[BibT_eX]

[DOI]

J. Algorithms, 1984

Worst-case Analysis of Set Union Algorithms.

[BibT_eX]

[DOI]

Jan van Leeuwen

J. ACM, 1984

Amortized Efficiency of List Update Rules

[BibT_eX]

[DOI]

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Scaling and Related Techniques for Geometry Problems

[BibT_eX]

[DOI]

Jon Louis Bentley

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.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1984

Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary)

[BibT_eX]

[DOI]

Uzi Vishkin

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Space-Efficient Implementations of Graph Search Methods.

[BibT_eX]

[DOI]

ACM Trans. Math. Softw., 1983

A Data Structure for Dynamic Trees.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1983

An Improved Algorithm for Hierarchical Clustering Using Strong Components.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1983

Updating a Balanced Search Tree in O(1) Rotations.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1983

Two new kinds of biased search trees.

[BibT_eX]

[DOI]

Joan Feigenbaum

Bell Syst. Tech. J., 1983

Self-Adjusting Binary Trees

[BibT_eX]

[DOI]

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Notes on introductory combinatorics.

[BibT_eX]

George Pólya

Donald R. Woods

Progress in computer science 4, Birkhäuser, ISBN: 978-3-7643-3170-2, 1983

Data structures and network algorithms.

[BibT_eX]

[DOI]

CBMS-NSF regional conference series in applied mathematics 44, SIAM, ISBN: 978-1-61197-026-5, 1983

1982

The Recognition of Series Parallel Digraphs.

[BibT_eX]

[DOI]

Jacobo Valdes

Eugene L. Lawler

SIAM J. Comput., 1982

Symbolic Program Analysis in Almost-Linear Time.

[BibT_eX]

[DOI]

John H. Reif

SIAM J. Comput., 1982

Asymptotically tight bounds on time-space trade-offs in a pebble game.

[BibT_eX]

[DOI]

J. ACM, 1982

Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1982

A Hierarchical Clustering Algorithm Using Strong Components.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1982

1981

On a Greedy Heuristic for Complete Matching.

[BibT_eX]

[DOI]

Edward M. Reingold

SIAM J. Comput., 1981

Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines.

[BibT_eX]

[DOI]

SIAM J. Comput., 1981

Fast Algorithms for Solving Path Problems.

[BibT_eX]

[DOI]

J. ACM, 1981

A Unified Approach to Path Problems.

[BibT_eX]

[DOI]

J. ACM, 1981

1980

Applications of a Planar Separator Theorem.

[BibT_eX]

[DOI]

Richard J. Lipton

SIAM J. Comput., 1980

The Pebbling Problem is Complete in Polynomial Space.

[BibT_eX]

[DOI]

John R. Gilbert

SIAM J. Comput., 1980

Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms.

[BibT_eX]

[DOI]

Edward G. Coffman Jr.

M. R. Garey

David S. Johnson

SIAM J. Comput., 1980

Design and Analysis of a Data Structure for Representing Sorted Lists.

[BibT_eX]

[DOI]

Mark R. Brown

SIAM J. Comput., 1980

Linear Expected-Time Algorithms for Connectivity Problems.

[BibT_eX]

[DOI]

Richard M. Karp

J. Algorithms, 1980

Variations on the Common Subexpression Problem.

[BibT_eX]

[DOI]

Peter J. Downey

Ravi Sethi

J. ACM, 1980

The Space Complexity of Pebble Games on Trees.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1980

Linear Expected-Time Algorithms for Connectivity Problems (Extended Abstract)

[BibT_eX]

[DOI]

Richard M. Karp

Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

Prime Subprogram Parsing of a Program.

[BibT_eX]

[DOI]

Proceedings of the Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, 1980

Biased 2-3 Trees

[BibT_eX]

[DOI]

Samuel W. Bent

Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980

1979

A Fast Algorithm for Finding Dominators in a Flowgraph.

[BibT_eX]

[DOI]

ACM Trans. Program. Lang. Syst., 1979

A Class of Algorithms which Require Nonlinear Time to Maintain Disjoint Sets.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1979

Applications of Path Compression on Balanced Trees.

[BibT_eX]

[DOI]

J. ACM, 1979

A Fast Merging Algorithm.

[BibT_eX]

[DOI]

Mark R. Brown

J. ACM, 1979

A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas.

[BibT_eX]

[DOI]

Bengt Aspvall

Michael F. Plass

Inf. Process. Lett., 1979

Storing a Sparse Table.

[BibT_eX]

[DOI]

Andrew Chi-Chih Yao

Commun. ACM, 1979

Upper and Lower Bounds on Time-Space Tradeoffs

[BibT_eX]

[DOI]

Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

Efficient Algorithms for Simple Matroid Intersection Problems

[BibT_eX]

[DOI]

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978

A Linear-Time Algorithm for Finding All Feedback Vertices.

[BibT_eX]

[DOI]

M. R. Garey

Inf. Process. Lett., 1978

Triangulating a Simple Polygon.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1978

Time-Space Trade-Offs in a Pebble Game.

[BibT_eX]

[DOI]

Wolfgang J. Paul

Acta Informatica, 1978

A Representation for Linear Lists with Movable Fingers

[BibT_eX]

[DOI]

Mark R. Brown

Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

1977

Corrigendum: Computing an st-Numbering. TCS 2(1976):339-344.

[BibT_eX]

Theor. Comput. Sci., 1977

Finding a Maximum Independent Set.

[BibT_eX]

[DOI]

Anthony E. Trojanowski

SIAM J. Comput., 1977

Finding optimum branchings.

[BibT_eX]

[DOI]

Networks, 1977

Correction: Space Bounds for a Game on Graphs.

[BibT_eX]

Wolfgang J. Paul

James R. Celoni

Math. Syst. Theory, 1977

Space Bounds for a Game on Graphs.

[BibT_eX]

[DOI]

Wolfgang J. Paul

James R. Celoni

Math. Syst. Theory, 1977

Reference Machines Require Non-linear Time to Maintain Disjoint Sets

[BibT_eX]

[DOI]

Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977

Application of a Planar Separator Theorem

[BibT_eX]

[DOI]

Richard J. Lipton

Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977

1976

Computing an st -Numbering.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1976

Algorithmic Aspects of Vertex Elimination on Graphs.

[BibT_eX]

[DOI]

Donald J. Rose

George S. Lueker

SIAM J. Comput., 1976

b-Matchings in Trees.

[BibT_eX]

[DOI]

Seymour E. Goodman

Stephen T. Hedetniemi

SIAM J. Comput., 1976

The Planar Hamiltonian Circuit Problem is NP-Complete.

[BibT_eX]

[DOI]

M. R. Garey

David S. Johnson

SIAM J. Comput., 1976

Augmentation Problems.

[BibT_eX]

[DOI]

Kapali P. Eswaran

SIAM J. Comput., 1976

Finding Minimum Spanning Trees.

[BibT_eX]

[DOI]

David R. Cheriton

SIAM J. Comput., 1976

Intersection graphs of curves in the plane.

[BibT_eX]

[DOI]

Gideon Ehrlich

J. Comb. Theory B, 1976

A Combinatorial Problem Which Is Complete in Polynomial Space.

[BibT_eX]

[DOI]

J. ACM, 1976

Lower bounds on the lengths of node sequences in directed graphs.

[BibT_eX]

[DOI]

George Markowsky

Discret. Math., 1976

Edge-Disjoint Spanning Trees and Depth-First Search.

[BibT_eX]

[DOI]

Acta Informatica, 1976

1975

Network Flow and Testing Graph Connectivity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1975

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

[BibT_eX]

[DOI]

Ronald C. Read

Networks, 1975

Efficiency of a Good But Not Linear Set Union Algorithm.

[BibT_eX]

[DOI]

J. ACM, 1975

Optimal Chain Partitions of Trees.

[BibT_eX]

[DOI]

Jayadev Misra

Inf. Process. Lett., 1975

Algorithmic Aspects of Vertex Elimination

[BibT_eX]

[DOI]

Donald J. Rose

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

1974

Finding Dominators in Directed Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 1974

Testing Flow Graph Reducibility.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1974

Efficient Planarity Testing.

[BibT_eX]

[DOI]

J. ACM, 1974

A Good Algorithm for Edge-Disjoint Branching.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1974

A New Algorithm for Finding Weak Components.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1974

A Note on Finding the Bridges of a Graph.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1974

Testing Graph Connectivity

[BibT_eX]

[DOI]

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

1973

Enumeration of the Elementary Circuits of a Directed Graph.

[BibT_eX]

[DOI]

SIAM J. Comput., 1973

Dividing a Graph into Triconnected Components.

[BibT_eX]

[DOI]

SIAM J. Comput., 1973

A V log V Algorithm for Isomorphism of Triconnected Planar Graphs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1973

Time Bounds for Selection.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1973

Efficient Algorithms for Graph Manipulation [H] (Algorithm 447).

[BibT_eX]

[DOI]

Commun. ACM, 1973

1972

Depth-First Search and Linear Graph Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 1972

Sorting Using Networks of Queues and Stacks.

[BibT_eX]

[DOI]

J. ACM, 1972

Determining Whether a Groupoid is a Group.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1972

Linear Time Bounds for Median Computations

[BibT_eX]

[DOI]

Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972

Isomorphism of Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of a symposium on the Complexity of Computer Computations, 1972

1971

An efficient planarity algorithm.

[BibT_eX]

[DOI]

PhD thesis, 1971

A V² Algorithm for Determining Isomorphism of Planar Graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1971

Planarity Testing in V log V Steps: Extended Abstract.

[BibT_eX]

Proceedings of the Information Processing, Proceedings of IFIP Congress 1971, Volume 1, 1971

Depth-First Search and Linear Graph Algorithms (Working Paper)

[BibT_eX]

[DOI]