Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time

DOI10.1006/jcss.1997.1538zbMath0897.68074OpenAlexW1969523663MaRDI QIDQ1384532

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

zbMATH Keywords

planar graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)

Related Items (7)

Minimum Cuts in Surface Graphs ⋮ Maximum flow in directed planar graphs with vertex capacities ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Lattices and Maximum Flow Algorithms in Planar Graphs ⋮ Accelerated Bend Minimization ⋮ Characterizing multiterminal flow networks and computing flows in networks of small treewidth ⋮ A fast algorithm for minimum weight odd circuits and cuts in planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Planar graphs: Theory and algorithms
• A data structure for dynamic trees
• Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
• The Lattice Structure of Flow in Planar Graphs
• Maximal Flow Through a Network
• TWO THEOREMS IN GRAPH THEORY
• An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
• A new approach to the maximum-flow problem
• Maximum Flow in Planar Networks
• Efficient Planarity Testing
• Faster shortest-path algorithms for planar graphs

This page was built for publication: Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time