Improved algorithms for min cut and max flow in undirected planar graphs

DOI10.1145/1993636.1993679zbMath1288.05276OpenAlexW2103099082WikidataQ61609454 ScholiaQ61609454MaRDI QIDQ5419101

Yahav Nussbaum, Piotr Sankowski, Giuseppe F. Italiano, Christian Wulff-Nilsen

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

planar graphdynamic algorithm\textsc{Max-flow}\textsc{Min-cut}

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (28)

Minimum Cuts in Surface Graphs ⋮ Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time ⋮ On the negative cost girth problem in planar networks ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Unnamed Item ⋮ 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 ⋮ Unnamed Item ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Shortest-path queries in static networks ⋮ Toroidal grid minors and stretch in embedded graphs ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Unnamed Item ⋮ Min-Cost Flow in Unit-Capacity Planar Graphs ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Faster algorithms for shortest path and network flow based on graph decomposition ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Non-crossing shortest paths in undirected unweighted planar graphs in linear time ⋮ 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: Improved algorithms for min cut and max flow in undirected planar graphs