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

DOI10.1137/0214045MaRDI QIDQ3680587zbMATH OpenOpenAlexFDO

Authors Refael Hassin, Donald B. Johnson

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

dualitygraph algorithmmaximum flowundirected planar flow network

Mathematics Subject Classification ID

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

Recommendations

• Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
• Faster shortest-path algorithms for planar graphs
• An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph
• Maximum flow in directed planar graphs with vertex capacities
• Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time

Cited in

(33)

• Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
• A linear algorithm for the all-bidirectional-edges problem on planar graphs
• Non-crossing shortest paths in undirected unweighted planar graphs in linear time
• Counting and sampling minimum cuts in genus \(g\) graphs
• An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph
• scientific article; zbMATH DE number 60387 (Why is no real title available?)
• Two flow network simplification algorithms
• Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
• Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs
• The binary network flow problem is logspace complete for P
• scientific article; zbMATH DE number 1769310 (Why is no real title available?)
• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
• scientific article; zbMATH DE number 742960 (Why is no real title available?)
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Improved Time Bounds for the Maximum Flow Problem
• Flow in planar graphs with vertex capacities
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• Max flow vitality in general and \(st\)-planar graphs
• Lattices and maximum flow algorithms in planar graphs
• Minimum flows in directed \(s\)-\(t\) planar networks
• Global minimum cuts in surface embedded graphs
• Parallel nested dissection for path algebra computations
• Minimum Cuts in Surface Graphs
• Faster shortest-path algorithms for planar graphs
• scientific article; zbMATH DE number 3941230 (Why is no real title available?)
• Maximum \(s\)-\(t\)-flow with \(k\) crossings in \(O(k^3 n \log n)\) time
• A Faster Deterministic Maximum Flow Algorithm
• Maximum flow in directed planar graphs with vertex capacities
• Fast and efficient solution of path algebra problems
• Flow in Planar Graphs with Multiple Sources and Sinks
• Algebraic tools for the construction of colored flows with boundary constraints
• Leveling the grid

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3680587)