We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
CLIQUE-WEB FACETS FOR MULTICUT POLYTOPES.
- Authors
Deza, M.; Grötschel, M.; Laurent, M.
- Abstract
Let G = (V, E) be a graph. An edge set {uv ϵ E|u ϵ Sj, i≠ j}, where S1, … Sk is a partition of V, is called a multicut with k shores. We investigate the polytopes MCk≤ (n) and MCMCk≤ (n) that are defined as the convex hulls of the incidence vectors of all multicuts with at most k shores and at least k shores, respectively, of the complete graph Kn. We introduce a large class of inequalities, called clique-web inequalities, valid for these poly- topes, and provide a quite complete characterization of those clique-web inequalities that define facets of MCMCk≤ (n) and MCMCk≤ (n). Using general facet manipulation techniques like collapsing and node splitting we construct further new classes of facets for these multicut polytopes. We also exhibit a class of clique-web facets for which the separation problem can be solved in polynomial time.
- Subjects
POLYTOPES; COMPLETE graphs; HYPERSPACE; GRAPHIC methods; MATHEMATICAL inequalities; TOPOLOGY; VECTOR analysis; GEOMETRICAL drawing
- Publication
Mathematics of Operations Research, 1992, Vol 17, Issue 4, p981
- ISSN
0364-765X
- Publication type
Article
- DOI
10.1287/moor.17.4.981