The Complexity of Multiterminal Cuts

DOI10.1137/S0097539792225297zbMath0809.68075WikidataQ56077927 ScholiaQ56077927MaRDI QIDQ4305362

Christos H. Papadimitriou, Elias Dahlhaus, Mihalis Yannakakis, P. D. Seymour, David S. Johnson

Publication date: 17 October 1994

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

partitioning; planar graphs; NP-completeness; network flow; multiterminal cut problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

90B10: Deterministic network models in operations research

Related Items

Unnamed Item, Primal-dual approximation algorithms for integral flow and multicut in trees, The planar multiterminal cut problem, Minimum multiway cuts in trees, Metrics with finite sets of primitive extensions, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, On weighted multiway cuts in trees, An improved approximation algorithm of MULTIWAY CUT., A characterization of minimizable metrics in the multifacility location problem, On embedding complete graphs into hypercubes, Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, The partition problem