Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time

DOI10.1137/0212005zbMath0501.68031OpenAlexW2068595367MaRDI QIDQ3967060

John H. Reif

Publication date: 1983

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0212005

zbMATH Keywords

graph algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)

Related Items (21)

Minimum Cuts in Surface Graphs ⋮ Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Parallel nested dissection for path algebra computations ⋮ Flow equivalent trees in undirected node-edge-capacitated planar graphs ⋮ Maximum weight independent set in trees ⋮ The planar multiterminal cut problem ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities ⋮ Faster shortest paths in dense distance graphs, with applications ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time ⋮ Fast and efficient solution of path algebra problems ⋮ Non-crossing shortest paths in undirected unweighted planar graphs in linear time ⋮ Unnamed Item ⋮ Flow in planar graphs with vertex capacities

This page was built for publication: Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time