Premium
On the multiway cut polyhedron
Author(s) -
Chopra Sunil,
Rao M. R.
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210106
Subject(s) - polyhedron , combinatorics , integer programming , mathematics , set (abstract data type) , graph , integer (computer science) , maximum cut , branch and cut , discrete mathematics , computer science , mathematical optimization , programming language
Abstract 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.