Maximum (s,t)-flows in planar networks in O(|V| |V|) time
From MaRDI portal
Publication:1384532
DOI10.1006/JCSS.1997.1538zbMATH Open0897.68074OpenAlexW1969523663MaRDI QIDQ1384532FDOQ1384532
Authors: Karsten Weihe 
Publication date: 4 August 1998
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1997.1538
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
Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)
Cites Work
- Network flows. Theory, algorithms, and applications.
- Maximal Flow Through a Network
- A data structure for dynamic trees
- Efficient Planarity Testing
- A new approach to the maximum-flow problem
- TWO THEOREMS IN GRAPH THEORY
- The Lattice Structure of Flow in Planar Graphs
- Faster shortest-path algorithms for planar graphs
- Planar graphs: Theory and algorithms
- Title not available (Why is that?)
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Maximum Flow in Planar Networks
- Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
Cited In (21)
- A linear algorithm for the all-bidirectional-edges problem on planar graphs
- Accelerated bend minimization
- Lattices and maximum flow algorithms in planar graphs
- 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 flows in planar dynamic networks with lower bounds
- Maximum flow in planar networks with exponentially distributed arc capacities
- Title not available (Why is that?)
- 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
- Multiple-source single-sink maximum flow in directed planar graphs in \(O(\mathrm{diameter} \cdot n \log n)\) time
- Minimum Cuts in Surface Graphs
- Maximum flow in directed planar graphs with vertex capacities
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Title not available (Why is that?)
- 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
- Maximum \(s\)-\(t\)-flow with \(k\) crossings in \(O(k^3 n \log n)\) time
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)
