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

DOI10.1137/0606068zbMath0572.05040OpenAlexW1983096342MaRDI QIDQ3689216

David B. Shmoys, Dorit S. Hochbaum

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

algorithmplanar graph3-cut

Mathematics Subject Classification ID

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

Related Items (4)

The planar multiterminal cut problem ⋮ Generating partitions of a graph into a fixed number of minimum weight cuts ⋮ On minimum 3-cuts and approximating k-cuts using Cut Trees ⋮ An improved approximation algorithm of MULTIWAY CUT.

This page was built for publication: An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem