Faster shortest-path algorithms for planar graphs
From MaRDI portal
Publication:5906822
DOI10.1006/JCSS.1997.1493zbMATH Open0880.68099OpenAlexW2762935521MaRDI QIDQ5906822FDOQ5906822
Authors: Satish Rao, Monika R. Henzinger, Philip N. Klein, 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
Recommendations
- Faster shortest-path algorithms for planar graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Dynamic algorithms for shortest paths in planar graphs
- scientific article; zbMATH DE number 219245
- Efficient parallel algorithms for shortest paths in planar graphs
- Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs
- Shortest path queries in planar graphs
- Efficient parallel algorithms for shortest paths in planar digraphs
- scientific article; zbMATH DE number 176745
Cites Work
- Generalized Nested Dissection
- Fibonacci heaps and their uses in improved network optimization algorithms
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- A Separator Theorem for Planar Graphs
- A Separator Theorem for Nonplanar Graphs
- Scaling Algorithms for the Shortest Paths Problem
- Faster algorithms for the shortest path problem
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Flow in Planar Graphs with Multiple Sources and Sinks
- A separator theorem for graphs of bounded genus
- An optimal algorithm for selection in a min-heap
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Planar separators and parallel polygon triangulation.
- Title not available (Why is that?)
- Fully dynamic planarity testing with applications
- Title not available (Why is that?)
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
- Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition
Cited In (93)
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Localized and compact data-structure for comparability graphs
- Shortest path computations in source-deplanarized graphs
- Planar and grid graph reachability problems
- Algorithms -- ESA '93. 1st annual European symposium Bad Honnef, Germany, September 30 -- October 2, 1993. Proceedings
- GENERALIZING MONOTONICITY: ON RECOGNIZING SPECIAL CLASSES OF POLYGONS AND POLYHEDRA
- Title not available (Why is that?)
- Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks
- Faster shortest paths in dense distance graphs, with applications
- A survey of the all-pairs shortest paths problem and its variants in graphs
- Faster shortest-path algorithms for planar graphs
- A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
- Approximation algorithms for polynomial-expansion and low-density graphs
- A dynamic programming approach for the pipe network layout problem
- Title not available (Why is that?)
- Faster approximate diameter and distance oracles in planar graphs
- Accelerated bend minimization
- Level-planar drawings with few slopes
- Many distances in planar graphs
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- How to draw the minimum cuts of a planar graph
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n \log^2 n)\)-time algorithm
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Single source shortest paths in \(H\)-minor free graphs
- Fully dynamic all pairs shortest paths with real edge weights
- Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
- Link Distance and Shortest Path Problems in the Plane
- Imposing contiguity constraints in political districting models
- Inverse obnoxious \(p\)-median location problems on trees with edge length modifications under different norms
- Exact distance oracles for planar graphs
- On the stabbing number of a random Delaunay triangulation
- Orthogonal graph drawing with flexibility constraints
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Planar Digraphs
- Computing the shortest essential cycle
- Flooding countries and destroying dams
- A simple algorithm for replacement paths problem
- The inverse 1-maxian problem with edge length modification
- How to walk your dog in the mountains with no magic leash
- Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- On the negative cost girth problem in planar networks
- Counting and sampling minimum cuts in genus \(g\) graphs
- Shortest-path queries in static networks
- Distance Labeling for Permutation Graphs
- Improved bounds for shortest paths in dense distance graphs
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- A simpler and more efficient algorithm for the next-to-shortest path problem
- Minimum Cuts in Surface Graphs
- 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
- Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
- A distributed shortest path algorithm for a planar network
- Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- Faster Approximate Diameter and Distance Oracles in Planar Graphs
- Shortest paths in time-dependent FIFO networks
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- Global minimum cuts in surface embedded graphs
- Optimally fast shortest path algorithms for some classes of graphs
- Fast generation of some classes of planar graphs
- I/O-efficient path traversal in succinct planar graphs
- Shortcutting Planar Digraphs
- Exploiting planarity in separation routines for the symmetric traveling salesman problem
- A fast algorithm for minimum weight odd circuits and cuts in planar graphs
- On the domino-parity inequalities for the STSP
- Non-crossing shortest paths in undirected unweighted planar graphs in linear time
- Title not available (Why is that?)
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Non-crossing shortest paths lengths in planar graphs in linear time
- An efficient oracle for counting shortest paths in planar graphs
- An efficient oracle for counting shortest paths in planar graphs
- Continuous mean distance of a weighted graph
- Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
- How vulnerable is an undirected planar graph with respect to max flow
- Path planning in a weighted planar subdivision under the Manhattan metric
- On matchings, T‐joins, and arc routing in road networks
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- Faster algorithms for shortest path and network flow based on graph decomposition
- How vulnerable is an undirected planar graph with respect to max flow
- Level-planar drawings with few slopes
- Disk-based shortest path discovery using distance index over large dynamic graphs
- Towards single face shortest vertex-disjoint paths in undirected planar graphs
- Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Non-crossing shortest paths lengths in planar graphs in linear time
- A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
- Short and simple cycle separators in planar graphs
- Algorithmic techniques for maintaining shortest routes in dynamic networks
This page was built for publication: Faster shortest-path algorithms for planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5906822)
