Faster shortest-path algorithms for planar graphs

DOI10.1145/195058.195092zbMath1345.05103OpenAlexW1979750070MaRDI QIDQ5890838

Satish B. Rao, Sairam Subramanian, Monika R. Henzinger, Philip N. Klein

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195092

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21)

Related Items

Maximum matchings in planar graphs via Gaussian elimination ⋮ Semi-dynamic shortest paths and breadth-first search in digraphs ⋮ The planar multiterminal cut problem ⋮ An efficient algorithm for shortest paths in vertical and horizontal segments ⋮ Linear-time algorithms for parametric minimum spanning tree problems on planar graphs ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Decomposable multi-parameter matroid optimization problems. ⋮ Fast separator decomposition for finite element meshes ⋮ Encoding shortest paths in spatial networks ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ A new approach for solving the network problems ⋮ Shortest path queries in digraphs of small treewidth ⋮ Improved algorithms for replacement paths problems in restricted graphs ⋮ An algorithm for computing simple \(k\)-factors ⋮ A uniform approach to semi-dynamic problems on digraphs ⋮ Linear-time algorithms for parametric minimum spanning tree problems on planar graphs ⋮ Finding the k Shortest Paths ⋮ Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs ⋮ A linear-time algorithm for edge-disjoint paths in planar graphs ⋮ Semi-dynamic breadth-first search in digraphs ⋮ An external memory data structure for shortest path queries