An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks

DOI10.1137/0214045zbMath0565.90018OpenAlexW1987197912MaRDI QIDQ3680587

Donald B. Johnson, Refael Hassin

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0214045

zbMATH Keywords

graph algorithmdualitymaximum flowundirected planar flow network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10)

Related Items (16)

Minimum Cuts in Surface Graphs ⋮ Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Parallel nested dissection for path algebra computations ⋮ Algebraic tools for the construction of colored flows with boundary constraints ⋮ Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time ⋮ Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities ⋮ Maximum flow in directed planar graphs with vertex capacities ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Faster shortest-path algorithms for planar graphs ⋮ Unnamed Item ⋮ Fast and efficient solution of path algebra problems ⋮ Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs ⋮ Non-crossing shortest paths in undirected unweighted planar graphs in linear time ⋮ Unnamed Item ⋮ Flow in planar graphs with vertex capacities

This page was built for publication: An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks