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