Shortest paths in directed planar graphs with negative lengths

DOI10.1145/1721837.1721846zbMath1300.05301WikidataQ60143024 ScholiaQ60143024MaRDI QIDQ2930306

Oren Weimann, Shay Mozes, Philip N. Klein

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1721837.1721846

zbMATH Keywords

planar graphs; shortest paths; replacement paths

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C38: Paths and cycles

05C10: Planar graphs; geometric and topological aspects of graph theory

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

Related Items

Unnamed Item, Shortest-path queries in static networks, Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles, Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time, Unnamed Item, Unnamed Item, Unnamed Item, Fault-tolerant distance labeling for planar graphs, Many distances in planar graphs, Fault-tolerant distance labeling for planar graphs, Minimum Cuts in Surface Graphs, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs, Counting and sampling minimum cuts in genus \(g\) graphs, On the negative cost girth problem in planar networks, Sublinear separators, fragility and subexponential expansion, Single source shortest paths in \(H\)-minor free graphs, Faster shortest paths in dense distance graphs, with applications, Single-source shortest paths and strong connectivity in dynamic planar graphs, Topologically trivial closed walks in directed surface graphs, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs