Faster shortest paths in dense distance graphs, with applications

DOI10.1016/j.tcs.2017.10.034zbMath1387.68187arXiv1404.0977WikidataQ60142999 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

zbMATH Keywords

planar graphs; shortest paths; dynamic range minimum queries; Monge heaps; recursive \(r\)-divisions

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Cites Work

• 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
• Shortest paths in directed planar graphs with negative lengths
• 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