Shortest paths in directed planar graphs with negative lengths
From MaRDI portal
Publication:2930306
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
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
Shortest-path queries in static networks, Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time, Unnamed Item, Unnamed Item, Unnamed Item, Many distances in 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, 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
