The planar multiterminal cut problem
From MaRDI portal
Publication:1130183
DOI10.1016/S0166-218X(98)00036-5zbMath0908.90259OpenAlexW1974901680MaRDI QIDQ1130183
Publication date: 20 August 1998
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://www.elsevier.com/locate/dam
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Abstract computational complexity for mathematical programming problems (90C60) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ Extended formulations for the \(A\)-cut problem ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ Disjoint paths in sparse graphs ⋮ Simple and improved parameterized algorithms for multiterminal cuts ⋮ Revisiting a simple algorithm for the planar multiterminal cut problem ⋮ A simple algorithm for multicuts in planar graphs with outer terminals ⋮ Political districting to minimize cut edges ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Matching theory
- Multiterminal flows and cuts
- Minimum Path Bases
- An improved algorithm for the planar 3-cut problem
- An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Solution Bases of Multiterminal Cut Problems
- Multi-Terminal Network Flows
- Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
- Selected Applications of Minimum Cuts in Networks
- On the multiway cut polyhedron
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- The Complexity of Multiterminal Cuts
- The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
- Faster shortest-path algorithms for planar graphs
