Faster Shortest-Path Algorithms for Planar Graphs
Journal of Computer and System SciencesPublished 1 August 1997Open access
Monika Henzinger, Philip N. Klein, Satish Rao, Sairam Subramanian
Citations410
SJR quartileQ1
SJR score1.03
SNIP1.08
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths and a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face are given.
Abstract
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we give an algorithm requiringO(n4/3 log(nL)) time, whereLis the absolute value of the most negative length. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bipartite graph, and for finding a maximum flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms.
Keywords
Computer Science
Journal of the ACMFibonacci heaps and their uses in improved network optimization algorithms
2,673 Citations1987Michael L. Fredman, Robert E. Tarjan
Using F-heaps, a new data structure for implementing heaps that extends the binomial queues proposed by Vuillemin and studied further by Brown, the improved bound for minimum spanning trees is the most striking.
SIAM Journal on Applied MathematicsA Separator Theorem for Planar Graphs
1,338 Citations1979Richard J. Lipton, Robert E. Tarjan
Journal of the ACMFaster algorithms for the shortest path problem
551 Citations1990Ravindra K. Ahuja, Kurt Mehlhorn +2 more
Efficient implementations of Dijkstra's shortest path algorithm are investigated and a new data structure, called the radix heap, is proposed for use in this algorithm.
SIAM Journal on Numerical AnalysisGeneralized Nested Dissection
549 Citations1979Richard J. Lipton, Donald J. Rose +1 more
It is shown that sparse Gaussian elimination is efficient for any class of graphs which have good separator, and conversely that graphs without good separators are not amenable to sparse GaRussian elimination.
SIAM Journal on ComputingFast Algorithms for Shortest Paths in Planar Graphs, with Applications
435 Citations1987Greg N. Federickson
Graph decomposition and data structures techniques are presented that exploit the structure of planar graphs to yield faster algorithms for a number of shortest path and related problems.
Journal of Computer and System SciencesTrans-dichotomous algorithms for minimum spanning trees and shortest paths
419 Citations1994Michael L. Fredman, Dan E. Willard
SIAM Journal on ComputingData Structures for On-Line Updating of Minimum Spanning Trees, with Applications
380 Citations1985Greg N. Frederickson
Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph.
Journal of AlgorithmsA separator theorem for graphs of bounded genus
257 Citations1984John R. Gilbert, Joan P. Hutchinson +1 more
The main result of this paper is that if the authors can draw a graph on a surface of genus g, then they can bisect it by removing $O(\sqrt{gn})$ vertices, best possible to within a constant factor.
Journal of the American Mathematical SocietyA separator theorem for nonplanar graphs
213 Citations1990Noga Alon, Paul Seymour +1 more
SIAM Journal on ComputingScaling Algorithms for the Shortest Paths Problem
168 Citations1995Andrew V. Goldberg
An O((square root of n)m log N) algorithm for the single-source shortest paths problem with integral arc lengths is given, which improves previous bounds for the problem.
A unified geometric approach to graph separators
166 Citations2002Gary L. Miller, Shang‐Hua Teng +1 more
A separator bound is proved for k-overlap graphs embedded in d dimensions, which unifies several earlier separator results.
SIAM Journal on ComputingFaster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
147 Citations1994Philip N. Klein, Serge Plotkin +2 more
New algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities are described, which are much faster than algorithms discovered previously.
Fast approximation algorithms for fractional packing and covering problems
119 Citations2002Serge Plotkin, David B. Shmoys +1 more
Fast algorithms that find approximate solutions for a general class of problems, which are called fractional packing and covering problems, are presented, and an important result is a theoretical analysis of the running time of a Lagrangian relaxation based algorithm.
SIAM Journal on ComputingFlow in Planar Graphs with Multiple Sources and Sinks
109 Citations1995Gary L. Miller, Joseph Naor
Journal of Computer and System SciencesPlanar Separators and Parallel Polygon Triangulation
108 Citations1995Michael T. Goodrich
The utility of such a separator decomposition is demonstrated by showing how it can be used in the design of a parallel algorithm for triangulating a simple polygon deterministically in O( log n) time using O(n/log n) processors on a CRCW PRAM.
Information and ComputationAn Optimal Algorithm for Selection in a Min-Heap
92 Citations1993Greg N. Frederickson
The result establishes a further example of a partial order for which the kth smallest element can be determined in time proportional to the information theory lower bound.
SIAM Journal on ComputingAn $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
54 Citations1985Refael Hassin, D. Barton Johnson
A new algorithm is given to find a maximum flow in an undirected planar flow network in O(n\log ^2 n) time, which is faster than the best method previously known by a factor of $\sqrt n /\log n$.
A parallel algorithm for finding a separator in planar graphs
52 Citations1987Hillel Gazit, Gary L. Miller
A randomized parallel algorithm for finding a simple cycle separator in a planar graph based on the solution of Lipton and Tarjan for the sequential case which takes O(n) time and combines with the Pan and Reif algorithm to find a BFS of planargraph in time O(log3(n)) using n1.5/log( n) processors.
Almost-optimum speed-ups of algorithms for bipartite matching and related problems
47 Citations1988Harold N. Gabow, Robert E. Tarjan
An algorithm for the assignment problem (minimum cost perfect bipartite matching) that improves the best known sequential algorithm, and is within a factor of log of the bestknown bound for the problem without costs (maximum cardinality matching).
Journal of the ACMParallel algorithms for minimum cuts and maximum flows in planar networks
37 Citations1987D. Barton Johnson
No efficient parallel algorithm is known for the maximum flow problem in general networks and when such a value is given, or when the computation is on an undirected network, the bound is O((logn)2) time using O(n4) processors.
Lecture notes in computer scienceMaintaining biconnected components of dynamic planar graphs
36 Citations1991Zvi Galil, Giuseppe F. Italiano
This work shows how to test at any time whether two vertices belong to the same biconnected component, and how to insert and delete an edge in O(n2/3) time in the worst case, where n is the number of vertices in the graph.
Lecture notes in computer scienceA fully dynamic data structure for reachability in planar digraphs
34 Citations1993Sairam Subramanian
A fully dynamic O(n)-space data structure is given to support an arbitrary sequence of operations that consist of adding new edges, deleting some existing edge, and querying to find out if a given node v is reachable in G by a directed path from another node u.
Efficient parallel shortest-paths in digraphs with a separator decomposition
20 Citations1993Edith Cohen
This paper presents an efficient parallel algorithms for families of graphs, where a separator decomposition either is provided with the input or is easily obtainable, and presents anNCalgorithm that computes shortest-paths from sources to all other vertices using O(n3?+s(n+n2?)) work.
Lecture notes in computer scienceA fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
17 Citations1993Philip N. Klein, Sairam Subramanian
A fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks given an error parameter e such that 0<e≤1, and the approximate paths are guaranteed to be accurate to within a (1+e)-factor.
Fully dynamic planarity testing (extended abstract)
14 Citations1992Zvi Galil, Giuseppe F. Italiano +1 more
This work shows how to support each of the above operations in 0(TZ2/3 ) time, where n is the number of vertices in the graph, and bound for tests and deletions is worst-case, while the bound for insertions is amortized.