Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
From MaRDI portal
Publication:5495844
DOI10.1145/2488608.2488702zbMath1293.90057OpenAlexW2040112642MaRDI QIDQ5495844
David Eisenstat, Philip N. Klein
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2488608.2488702
Combinatorial optimization (90C27) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21)
Related Items (12)
Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ Faster shortest paths in dense distance graphs, with applications ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Unnamed Item ⋮ A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs ⋮ On almost Monge all scores matrices ⋮ Unnamed Item ⋮ Non-crossing shortest paths in undirected unweighted planar graphs in linear time
This page was built for publication: Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
