On the multiway cut polyhedron

Sunil Chopra*, M. R. Rao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

60 Scopus citations


Given a graph G = V,E and a set N ⊆ V, we consider the problem of finding a minimum‐weight multiway cut that separates each pair of nodes in N. In this paper we give an integer programming formulation of this problem and study the associated polyhedron. We give some computational results to support the strength of our facets. We also give some efficiently solvable instances.

Original languageEnglish (US)
Pages (from-to)51-89
Number of pages39
Issue number1
StatePublished - Jan 1 1991

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'On the multiway cut polyhedron'. Together they form a unique fingerprint.

Cite this