Faster shortest paths in dense distance graphs, with applications
From MaRDI portal
Publication:1698725
DOI10.1016/j.tcs.2017.10.034zbMath1387.68187arXiv1404.0977OpenAlexW2107848307WikidataQ60142999 ScholiaQ60142999MaRDI QIDQ1698725
Shay Mozes, Yahav Nussbaum, Oren Weimann
Publication date: 16 February 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.0977
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum flow in directed planar graphs with vertex capacities
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Fractional cascading. I: A data structuring technique
- The minimum spanning tree problem on a planar graph
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Multiple-Source Shortest Paths in Embedded Graphs
- Maximum st-Flow in Directed Planar Graphs via Shortest Paths
- Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
- The Lattice Structure of Flow in Planar Graphs
- An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Maximum Flow in Planar Networks
- Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
- Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
- Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications
- Improved Submatrix Maximum Queries in Monge Matrices
- Improved Distance Queries in Planar Graphs
- Fibonacci heaps and their uses in improved network optimization algorithms
- Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
- Improved algorithms for min cut and max flow in undirected planar graphs
- Structured recursive separator decompositions for planar graphs in linear time
- Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
- Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs
- Computing the Girth of a Planar Graph in Linear Time
- Faster shortest-path algorithms for planar graphs
- Many distances in planar graphs
This page was built for publication: Faster shortest paths in dense distance graphs, with applications