Faster shortest-path algorithms for planar graphs
From MaRDI portal
Publication:5906822
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
- scientific article; zbMATH DE number 176746 (Why is no real title available?)
- scientific article; zbMATH DE number 871900 (Why is no real title available?)
- A Separator Theorem for Nonplanar Graphs
- A Separator Theorem for Planar Graphs
- A separator theorem for graphs of bounded genus
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- An optimal algorithm for selection in a min-heap
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
- Faster algorithms for the shortest path problem
- Fibonacci heaps and their uses in improved network optimization algorithms
- Flow in Planar Graphs with Multiple Sources and Sinks
- Fully dynamic planarity testing with applications
- Generalized Nested Dissection
- Planar separators and parallel polygon triangulation.
- Scaling Algorithms for the Shortest Paths Problem
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
Cited in
(93)- Shortest path computations in source-deplanarized graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Localized and compact data-structure for comparability 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
- scientific article; zbMATH DE number 176745 (Why is no real title available?)
- scientific article; zbMATH DE number 7561410 (Why is no real title available?)
- 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
- 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
- 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
- Faster approximate diameter and distance oracles in planar graphs
- Non-crossing shortest paths lengths in planar graphs in linear time
- scientific article; zbMATH DE number 7378687 (Why is no real title available?)
- How to draw the minimum cuts of a planar graph
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- Accelerated bend minimization
- Level-planar drawings with few slopes
- Many distances in planar graphs
- Single source shortest paths in H-minor free graphs
- An efficient oracle for counting shortest paths in planar graphs
- An efficient oracle for counting shortest paths in planar graphs
- 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
- Continuous mean distance of a weighted graph
- Fully dynamic all pairs shortest paths with real edge weights
- Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
- Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
- Link Distance and Shortest Path Problems in the Plane
- Inverse obnoxious \(p\)-median location problems on trees with edge length modifications under different norms
- On the stabbing number of a random Delaunay triangulation
- Imposing contiguity constraints in political districting models
- Orthogonal graph drawing with flexibility constraints
- Exact distance oracles for planar graphs
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Planar Digraphs
- Computing the shortest essential cycle
- How vulnerable is an undirected planar graph with respect to max flow
- Flooding countries and destroying dams
- Path planning in a weighted planar subdivision under the Manhattan metric
- On matchings, T‐joins, and arc routing in road networks
- Faster algorithms for shortest path and network flow based on graph decomposition
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- A simple algorithm for replacement paths problem
- The inverse 1-maxian problem with edge length modification
- 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
- How to walk your dog in the mountains with no magic leash
- Shortest-path queries in static networks
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- How vulnerable is an undirected planar graph with respect to max flow
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Distance Labeling for Permutation Graphs
- Improved bounds for shortest paths in dense distance graphs
- Level-planar drawings with few slopes
- 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
- A simpler and more efficient algorithm for the next-to-shortest path problem
- Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
- Minimum Cuts in Surface Graphs
- Disk-based shortest path discovery using distance index over large dynamic graphs
- A distributed shortest path algorithm for a planar network
- Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
- Towards single face shortest vertex-disjoint paths in undirected planar graphs
- 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
- Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
- Shortest paths in time-dependent FIFO networks
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
- Non-crossing shortest paths lengths in planar graphs in linear time
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- Short and simple cycle separators in planar graphs
- Global minimum cuts in surface embedded graphs
- Fast generation of some classes of planar graphs
- Optimally fast shortest path algorithms for some classes of graphs
- Algorithmic techniques for maintaining shortest routes in dynamic networks
- I/O-efficient path traversal in succinct planar graphs
- 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
- Shortcutting Planar Digraphs
- Non-crossing shortest paths in undirected unweighted planar graphs in linear time
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)
