Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs

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

zbMATH Keywords

combinatorial optimizationplanar graphsmax flowMenger problemmultiple-source shortest paths

Mathematics Subject Classification ID

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