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
(36)- Shortest path computations in source-deplanarized graphs
- An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane
- Multiple-source shortest paths in planar graphs
- Faster shortest paths in dense distance graphs, with applications
- Topologically trivial closed walks in directed surface graphs
- Tiling with Squares and Packing Dominos in Polynomial Time
- Non-crossing shortest paths lengths in planar graphs in linear time
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- Accelerated bend minimization
- Level-planar drawings with few slopes
- Single source shortest paths in H-minor free graphs
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n \log^2 n)\)-time algorithm
- Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
- Fault-tolerant distance labeling for planar graphs
- Fault-tolerant distance labeling for planar graphs
- Exact distance oracles for planar graphs
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Almost optimal exact distance oracles for planar graphs
- Fast domino tileability
- An almost optimal edit distance oracle
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Counting and sampling minimum cuts in genus g graphs
- Simplifying and unifying replacement paths algorithms in weighted directed graphs
- Improved bounds for shortest paths in dense distance graphs
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Level-planar drawings with few slopes
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm
- Distributed planar reachability in nearly optimal time
- Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
- Negative-weight single-source shortest paths in near-linear time
- Solving the replacement paths problem for planar directed graphs in O(n n) 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
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)
