Shortest paths in directed planar graphs with negative lengths: a linear-space O(n^2 n)-time algorithm
From MaRDI portal
Publication:6486937
Recommendations
- 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
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- scientific article; zbMATH DE number 3922691
- Non-crossing shortest paths lengths in planar graphs in linear time
- Non-crossing shortest paths in undirected unweighted planar graphs in linear time
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Dijkstra-based algorithms for the shortest path problem with edges of negative length
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
Cited in
(30)- Faster shortest paths in dense distance graphs, with applications
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Topologically trivial closed walks in directed surface graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n \log^2 n)\)-time algorithm
- Counting and sampling minimum cuts in genus g graphs
- Finding an Even Simple Path in a Directed Planar Graph
- Near-optimal distance emulator for planar graphs
- Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
- Shortest-path queries in static networks
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- Solving the replacement paths problem for planar directed graphs in O(n n) time
- Exact distance oracles for planar graphs
- Single source distance oracle for planar digraphs avoiding a failed node or link
- Global minimum cuts in surface embedded graphs
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Minimum Cuts in Surface Graphs
- Fault-tolerant distance labeling for planar graphs
- Many distances in planar graphs
- Fault-tolerant distance labeling for planar graphs
- Non-crossing shortest paths lengths in planar graphs in linear time
- Near optimal algorithm for the directed single source replacement paths problem
- Negative-weight single-source shortest paths in near-linear time
- On the negative cost girth problem in planar networks
- Sublinear separators, fragility and subexponential expansion
- Single source shortest paths in H-minor free graphs
This page was built for publication: Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6486937)
