Faster shortest-path algorithms for planar graphs

DOI10.1006/jcss.1997.1493zbMath0880.68099OpenAlexW2762935521MaRDI QIDQ5906822

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

Publication date: 28 October 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1493

zbMATH Keywords

linear-time algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Minimum Cuts in Surface Graphs, Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time, How to draw the minimum cuts of a planar graph, Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, A survey of the all-pairs shortest paths problem and its variants in graphs, Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Inverse obnoxious $p$-median location problems on trees with edge length modifications under different norms, A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes, Dynamic shortest paths and transitive closure: algorithmic techniques and data structures, A simple algorithm for replacement paths problem, On the stabbing number of a random Delaunay triangulation, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Imposing Contiguity Constraints in Political Districting Models, Computing the shortest essential cycle, Multicuts in planar and bounded-genus graphs with bounded number of terminals, Maximum $(s,t)$-flows in planar networks in $\mathcal O(|V| \log |V|)$ time, Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs, Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time, Continuous mean distance of a weighted graph, On the negative cost girth problem in planar networks, Non-crossing shortest paths lengths in planar graphs in linear time, How vulnerable is an undirected planar graph with respect to max flow, On matchings, T‐joins, and arc routing in road networks, Non-crossing shortest paths lengths in planar graphs in linear time, A simpler and more efficient algorithm for the next-to-shortest path problem, Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities, Shortest paths in time-dependent FIFO networks, Faster shortest paths in dense distance graphs, with applications, Path planning in a weighted planar subdivision under the Manhattan metric, How vulnerable is an undirected planar graph with respect to max flow, On shortest disjoint paths in planar graphs, Link distance and shortest path problems in the plane, Maximum flow in directed planar graphs with vertex capacities, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Unnamed Item, Counting and sampling minimum cuts in genus $g$ graphs, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Orthogonal graph drawing with flexibility constraints, Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks, A dynamic programming approach for the pipe network layout problem, The inverse 1-maxian problem with edge length modification, A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals, Efficient vertex-label distance oracles for planar graphs, Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Faster approximate diameter and distance oracles in planar graphs, FLOODING COUNTRIES AND DESTROYING DAMS, Shortest-path queries in static networks, Fully dynamic all pairs shortest paths with real edge weights, Planar graphs, negative weight edges, shortest paths, and near linear time, On the domino-parity inequalities for the STSP, Single source shortest paths in $H$-minor free graphs, Efficient dynamic approximate distance oracles for vertex-labeled planar graphs, Unnamed Item, How to walk your dog in the mountains with no magic leash, Planar and grid graph reachability problems, Level-planar drawings with few slopes, Disk-based shortest path discovery using distance index over large dynamic graphs, GENERALIZING MONOTONICITY: ON RECOGNIZING SPECIAL CLASSES OF POLYGONS AND POLYHEDRA, Level-planar drawings with few slopes, An efficient oracle for counting shortest paths in planar graphs, Accelerated Bend Minimization, Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization, Many distances in planar graphs, Link Distance and Shortest Path Problems in the Plane, Localized and compact data-structure for comparability graphs, Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation, Faster Approximate Diameter and Distance Oracles in Planar Graphs, Planar Digraphs, Non-crossing shortest paths in undirected unweighted planar graphs in linear time, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, Unnamed Item, Unnamed Item, Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks, An efficient oracle for counting shortest paths in planar graphs, Distance Labeling for Permutation Graphs, Short and Simple Cycle Separators in Planar Graphs, A fast algorithm for minimum weight odd circuits and cuts in planar graphs

Cites Work