An O ( | V |^2 ) Algorithm for the Planar 3-Cut Problem

DOI10.1137/0606068MaRDI QIDQ3689216zbMATH OpenOpenAlexFDO

Authors Dorit S. Hochbaum, David B. Shmoys

Publication date 1985

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0606068

zbMATH Keywords

3-cutalgorithmplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Connectivity (05C40) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An improved algorithm for the planar 3-cut problem
• scientific article; zbMATH DE number 4195169
• A simple algorithm for the planar multiway cut problem
• A polynomial-time approximation scheme for planar multiway cut
• A new and improved algorithm for the 3-cut problem
• scientific article; zbMATH DE number 6850401
• Revisiting a simple algorithm for the planar multiterminal cut problem
• A tight \(\sqrt{2} \)-approximation for linear 3-cut
• An efficient algorithm for packing cuts and (2,3)-metrics in a planar graph with three holes
• scientific article; zbMATH DE number 6469225

Cited in

(19)

• Min Cut is NP-complete for edge weighted trees
• The planar multiterminal cut problem
• A new and improved algorithm for the 3-cut problem
• An improved approximation algorithm of MULTIWAY CUT.
• Generating partitions of a graph into a fixed number of minimum weight cuts
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• Minimal disconnected cuts in planar graphs
• Finding first, second and third order graphs cuts
• An improved algorithm for the planar 3-cut problem
• scientific article; zbMATH DE number 4195169 (Why is no real title available?)
• Solving minimum K-cardinality cut problems in planar graphs
• scientific article; zbMATH DE number 512927 (Why is no real title available?)
• scientific article; zbMATH DE number 6850401 (Why is no real title available?)
• Minimal disconnected cuts in planar graphs
• On minimum 3-cuts and approximating k-cuts using cut trees
• scientific article; zbMATH DE number 3999696 (Why is no real title available?)
• Finding all convex cuts of a plane graph in cubic time
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
• Packings of cuts realizing distances between certain vertices in a planar graph

This page was built for publication: An $O ( | V |^2 )$ 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 Q3689216)