Shortest paths in planar graphs with real lengths in O(n ^2 n/ n) time

DOI10.1007/978-3-642-15781-3_18MaRDI QIDQ3586397zbMATHOpenAlexWikidataFDO

Authors Shay Mozes, Christian Wulff-Nilsen

Publication date 6 September 2010

Published in Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15781-3_18

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

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

(32)

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