Shortest paths in planar graphs with real lengths in O(n ^2 n/ n) time
From MaRDI portal
Publication:3586397
Recommendations
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n \log^2 n)\)-time algorithm
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Faster shortest-path algorithms for planar graphs
- Multiple-source shortest paths in planar graphs
Cited in
(32)- Solving the replacement paths problem for planar directed graphs in \(O(n\log n)\) time
- Counting and sampling minimum cuts in genus \(g\) graphs
- Multiple-source shortest paths in planar graphs
- Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
- Tiling with Squares and Packing Dominos in Polynomial Time
- Single source shortest paths in \(H\)-minor free graphs
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm
- Non-crossing shortest paths lengths in planar graphs in linear time
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Exact distance oracles for planar graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Faster shortest paths in dense distance graphs, with applications
- Improved bounds for shortest paths in dense distance graphs
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Distributed planar reachability in nearly optimal time
- Accelerated bend minimization
- Topologically trivial closed walks in directed surface graphs
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane
- Global minimum cuts in surface embedded graphs
- Fast domino tileability
- Short and simple cycle separators in planar graphs
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n \log^2 n)\)-time algorithm
- Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
- Shortest path computations in source-deplanarized graphs
- Level-planar drawings with few slopes
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
- Level-planar drawings with few slopes
- Fault-tolerant distance labeling for planar graphs
- Fault-tolerant distance labeling for planar graphs
This page was built for publication: Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586397)
