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

DOI10.1007/978-3-642-15781-3_18zbMATH Open1287.05073OpenAlexW1527270374WikidataQ60143025 ScholiaQ60143025MaRDI QIDQ3586397FDOQ3586397

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

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
• 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

Mathematics Subject Classification ID

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

Cited In (31)

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