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

Christian Wulff-Nilsen, Shay Mozes

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 (27)

• 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
• Faster shortest paths in dense distance graphs, with applications
• Topologically trivial closed walks in directed surface graphs
• Level-planar drawings with few slopes
• Title not available (Why is that?)
• 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.
• Title not available (Why is that?)
• Fast domino tileability
• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
• Title not available (Why is that?)
• Short and Simple Cycle Separators in Planar Graphs
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
• Counting and sampling minimum cuts in genus \(g\) graphs
• Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths
• 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
• Accelerated Bend Minimization
• Title not available (Why is that?)

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)