A simple algorithm for the planar multiway cut problem

DOI10.1006/JAGM.2000.1148MaRDI QIDQ2731602zbMATH OpenOpenAlexFDO

Authors W. Yeh

Publication date 12 December 2001

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.2000.1148

zbMATH Keywords

min-cut problem\(k\)-way cut

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• The planar multiterminal cut problem
• A simple algorithm for the multiway cut problem
• A polynomial-time approximation scheme for planar multiway cut
• The Complexity of Multiterminal Cuts
• scientific article; zbMATH DE number 2081002

Cited in

(13)

• Algorithms for Multiterminal Cuts
• A simple algorithm for the multiway cut problem
• Revisiting a simple algorithm for the planar multiterminal cut problem
• scientific article; zbMATH DE number 4195169 (Why is no real title available?)
• A tight lower bound for planar multiway cut with fixed number of terminals
• Generating partitions of a graph into a fixed number of minimum weight cuts
• Multiple Cuts in Separating Plane Algorithms
• Simple and improved parameterized algorithms for multiterminal cuts
• A cutting plane algorithm for the general routing problem
• New results on planar and directed multicuts
• The maximum integer multiterminal flow problem in directed graphs
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: A simple algorithm for the planar multiway cut problem

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