Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
From MaRDI portal
Publication:3967060
DOI10.1137/0212005zbMath0501.68031MaRDI QIDQ3967060
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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
90B10: Deterministic network models in operations research
Related Items
Counting and sampling minimum cuts in genus \(g\) graphs, Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time, Flow equivalent trees in undirected node-edge-capacitated planar graphs, Parallel nested dissection for path algebra computations, Maximum weight independent set in trees, The planar multiterminal cut problem, Flow in planar graphs with vertex capacities, Fast and efficient solution of path algebra problems, Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities