Maximum (s,t)-flows in planar networks in O(|V| |V|) time
From MaRDI portal
Publication:1384532
Recommendations
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- 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
- Maximum Flow in Directed Planar Graphs with Vertex Capacities
Cites work
- scientific article; zbMATH DE number 3314878 (Why is no real title available?)
- A data structure for dynamic trees
- A new approach to the maximum-flow problem
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
- Efficient Planarity Testing
- Faster shortest-path algorithms for planar graphs
- Maximal Flow Through a Network
- Maximum Flow in Planar Networks
- Network flows. Theory, algorithms, and applications.
- Planar graphs: Theory and algorithms
- TWO THEOREMS IN GRAPH THEORY
- The Lattice Structure of Flow in Planar Graphs
Cited in
(21)- Maximum \(s\)-\(t\)-flow with \(k\) crossings in \(O(k^3 n \log n)\) time
- A linear algorithm for the all-bidirectional-edges problem on planar graphs
- Lattices and maximum flow algorithms in planar graphs
- Accelerated bend minimization
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
- Maximum flow in planar networks with exponentially distributed arc capacities
- Maximum flows in planar dynamic networks with lower bounds
- Counting and sampling minimum cuts in genus g graphs
- scientific article; zbMATH DE number 6297748 (Why is no real title available?)
- Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
- Maximum flow in directed planar graphs with vertex capacities
- Multiple-source single-sink maximum flow in directed planar graphs in \(O(\mathrm{diameter} \cdot n \log n)\) time
- Minimum Cuts in Surface Graphs
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- scientific article; zbMATH DE number 3941230 (Why is no real title available?)
- Maximum Flow in Directed Planar Graphs with Vertex Capacities
- An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- A fast algorithm for minimum weight odd circuits and cuts in planar graphs
- Maximum \(k\)-splittable \(s, t\)-flows
This page was built for publication: Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1384532)
