The planar multiterminal cut problem

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

Authors: 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

Recommendations

• scientific article; zbMATH DE number 2081002
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• The Complexity of Multiterminal Cuts
• scientific article; zbMATH DE number 176254

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

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Matching theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Multiterminal Cuts
• Title not available (Why is that?)
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Multi-Terminal Network Flows
• On the multiway cut polyhedron
• Title not available (Why is that?)
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Faster shortest-path algorithms for planar graphs
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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 (20)

• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• Minimum planar multi-sink cuts with connectivity priors
• Disjoint paths in sparse graphs
• Algorithms for Multiterminal Cuts
• Revisiting a simple algorithm for the planar multiterminal cut problem
• A tight lower bound for planar multiway cut with fixed number of terminals
• Title not available (Why is that?)
• Extended formulations for the \(A\)-cut problem
• Simple and improved parameterized algorithms for multiterminal cuts
• A simple algorithm for multicuts in planar graphs with outer terminals
• Solving minimum K-cardinality cut problems in planar graphs
• A simple algorithm for the planar multiway cut problem
• Crossing properties of multiterminal cuts
• An improved algorithm for the planar 3-cut problem
• The problem of \(\Pi_{2}\)-cut-introduction
• Title not available (Why is that?)
• 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
• A polynomial-time approximation scheme for planar multiway cut

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)