Revisiting a simple algorithm for the planar multiterminal cut problem

DOI10.1016/J.ORL.2010.03.003MaRDI QIDQ991478zbMATH OpenOpenAlexFDO

Authors Kevin K. H. Cheung, Kyle Harvey

Publication date 7 September 2010

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2010.03.003

zbMATH Keywords

algorithmcounterexampleplanar graphmultiterminal cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 2081002
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• The planar multiterminal cut problem
• The Complexity of Multiterminal Cuts

Cites work

• A simple algorithm for the planar multiway cut problem
• New results on planar and directed multicuts
• The Complexity of Multiterminal Cuts
• The planar multiterminal cut problem

Cited in

(7)

• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• scientific article; zbMATH DE number 4195169 (Why is no real title available?)
• Simple and improved parameterized algorithms for multiterminal cuts
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
• A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs

This page was built for publication: Revisiting a simple algorithm for the planar multiterminal cut problem

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