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
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals, Unnamed Item, Minimum Cuts in Surface Graphs, Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time, Non-crossing shortest paths lengths in planar graphs in linear time, How vulnerable is an undirected planar graph with respect to max flow, 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, Faster shortest paths in dense distance graphs, with applications, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, Fast and efficient solution of path algebra problems, Non-crossing shortest paths in undirected unweighted planar graphs in linear time, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
