Planar graphs, negative weight edges, shortest paths, and near linear time
From MaRDI portal
Publication:2496320
Recommendations
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- 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
- Dynamic algorithms for shortest paths in planar graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
Cites work
- A note on two problems in connexion with graphs
- A Separator Theorem for Planar Graphs
- Compact oracles for reachability and approximate distances in planar digraphs
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Faster Scaling Algorithms for Network Problems
- Faster shortest-path algorithms for planar graphs
- Finding small simple cycle separators for 2-connected planar graphs
- Flow in Planar Graphs with Multiple Sources and Sinks
- Generalized Nested Dissection
- scientific article; zbMATH DE number 4068901 (Why is no real title available?)
- scientific article; zbMATH DE number 176745 (Why is no real title available?)
- scientific article; zbMATH DE number 1433426 (Why is no real title available?)
- scientific article; zbMATH DE number 6469225 (Why is no real title available?)
- scientific article; zbMATH DE number 3225808 (Why is no real title available?)
- Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
- Multiple-source shortest paths in planar graphs
- On a routing problem
- The Discrete Geodesic Problem
- Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems
Cited in
(52)- Faster shortest paths in dense distance graphs, with applications
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- 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
- 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 path queries in planar graphs
- Paths of low weight in planar graphs
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- Engineering Route Planning Algorithms
- 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
- Improved bounds for shortest paths in dense distance graphs
- NC algorithms for weighted planar perfect matching and related problems
- Near-optimal distance emulator for planar graphs
- Decremental SPQR-trees for Planar Graphs
- A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
- Min-Cost Flow in Unit-Capacity Planar Graphs
- A divide-and-conquer algorithm for two-point L₁ shortest path queries in polygonal domains
- scientific article; zbMATH DE number 7561410 (Why is no real title available?)
- Exploiting hopsets: improved distance oracles for graphs of constant highway dimension and beyond
- Shortest-path queries in static networks
- Short and simple cycle separators in planar graphs
- A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- Computing large matchings in planar graphs with fixed minimum degree
- Exact distance oracles for planar graphs
- Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Minimum Cuts in Surface Graphs
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Faster shortest-path algorithms for planar graphs
- Accelerated bend minimization
- Level-planar drawings with few slopes
- Fault-tolerant distance labeling for planar graphs
- Many distances in planar graphs
- Fault-tolerant distance labeling for planar graphs
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm
- Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
- Distributed planar reachability in nearly optimal time
- Fully dynamic strongly connected components in planar digraphs
- Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
- Negative-weight single-source shortest paths in near-linear time
- Almost optimal exact distance oracles for planar graphs
- An almost optimal edit distance oracle
- Fully dynamic algorithms for minimum weight cycle and related problems
- Bounded weighted edit distance: dynamic algorithms and matching lower bounds
- Core-sparse Monge matrix multiplication: improved algorithm and applications
- Faster construction of a planar distance oracle with \(\tilde{O}(1)\) query time
- On the negative cost girth problem in planar networks
- Single source shortest paths in H-minor free graphs
This page was built for publication: Planar graphs, negative weight edges, shortest paths, and near linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2496320)
