The planar multiterminal cut problem

DOI10.1016/S0166-218X(98)00036-5zbMATH Open0908.90259OpenAlexW1974901680MaRDI QIDQ1130183FDOQ1130183

David Hartvigsen

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

zbMATH Keywords

minimum weight set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Matching theory
• The Complexity of Multiterminal Cuts
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Multi-Terminal Network Flows
• On the multiway cut polyhedron
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Faster shortest-path algorithms for planar graphs
• Selected Applications of Minimum Cuts in Networks
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
• Solution Bases of Multiterminal Cut Problems
• Minimum Path Bases
• An improved algorithm for the planar 3-cut problem
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• Multiterminal flows and cuts

Cited In (12)

• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• Disjoint paths in sparse graphs
• Revisiting a simple algorithm for the planar multiterminal cut problem
• Extended formulations for the \(A\)-cut problem
• Multicuts in planar and bounded-genus graphs with bounded number of terminals
• Simple and improved parameterized algorithms for multiterminal cuts
• A simple algorithm for multicuts in planar graphs with outer terminals
• Title not available (Why is that?)
• The problem of \(\Pi_{2}\)-cut-introduction
• A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
• FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
• Political districting to minimize cut edges

This page was built for publication: The planar multiterminal cut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1130183)