An improved algorithm for the planar 3-cut problem

DOI10.1016/0196-6774(91)90021-PMaRDI QIDQ3197351zbMATH OpenOpenAlexFDO

Authors Xin He

Publication date 1991

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

Full work available at URL https://doi.org/10.1016/0196-6774(91)90021-p

zbMATH Keywords

planar 3-cut problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• A new and improved algorithm for the 3-cut problem
• scientific article; zbMATH DE number 4195169
• On minimum 3-cuts and approximating k-cuts using cut trees
• The planar multiterminal cut problem

Cited in

(11)

• Min Cut is NP-complete for edge weighted trees
• The planar multiterminal cut problem
• A new and improved algorithm for the 3-cut problem
• The critical node detection problem in networks: a survey
• Generating partitions of a graph into a fixed number of minimum weight cuts
• Minimal disconnected cuts in planar graphs
• Finding first, second and third order graphs cuts
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• scientific article; zbMATH DE number 2081002 (Why is no real title available?)
• Minimal disconnected cuts in planar graphs
• On minimum 3-cuts and approximating k-cuts using cut trees

This page was built for publication: An improved algorithm for the planar 3-cut problem

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