Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
From MaRDI portal
Publication:3967060
DOI10.1137/0212005zbMath0501.68031OpenAlexW2068595367MaRDI 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
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
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
