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 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
- 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
- scientific article; zbMATH DE number 3314878 (Why is no real title available?)
- Maximal Flow Through a Network
- Maximum Flow in Planar Networks
- Network flows. Theory, algorithms, and applications.
- Planar graphs: Theory and algorithms
- The Lattice Structure of Flow in Planar Graphs
- TWO THEOREMS IN GRAPH THEORY
Cited in
(23)- A linear algorithm for the all-bidirectional-edges problem on planar graphs
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Maximum s-t-flow with k crossings in O(k^3 n n) time
- Lattices and maximum flow algorithms in planar graphs
- An O(n n) algorithm for maximum st-flow in a directed planar graph
- Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
- Maximum Flow in Directed Planar Graphs with Vertex Capacities
- An O(n\log ^2 n) Algorithm for Maximum Flow in Undirected Planar Networks
- scientific article; zbMATH DE number 3941230 (Why is no real title available?)
- Maximum flow in planar networks with exponentially distributed arc capacities
- Minimum flows in (s,t) planar networks
- Maximum flows in planar dynamic networks with lower bounds
- Counting and sampling minimum cuts in genus g graphs
- Multiple-source single-sink maximum flow in directed planar graphs in \(O(\mathrm{diameter} \cdot n \log n)\) time
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- 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
- Minimum Cuts in Surface Graphs
- Accelerated bend minimization
- Maximum flow in directed planar graphs with vertex capacities
- Nested dissection meets IPMs: planar min-cost flow in nearly-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)
