An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
From MaRDI portal
Publication:3680587
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
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
