Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time

DOI10.1007/978-3-642-15781-3_18zbMath1287.05073OpenAlexW1527270374WikidataQ60143025 ScholiaQ60143025MaRDI QIDQ3586397

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

Mathematics Subject Classification ID

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

Related Items (20)

Fast domino tileability ⋮ Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time ⋮ Tiling with Squares and Packing Dominos in Polynomial Time ⋮ Unnamed Item ⋮ Faster shortest paths in dense distance graphs, with applications ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Topologically trivial closed walks in directed surface graphs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs ⋮ Level-planar drawings with few slopes ⋮ Level-planar drawings with few slopes ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Accelerated Bend Minimization ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fault-tolerant distance labeling for planar 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(nlog2 n/loglogn) Time