ON THE K-CUT SUBGRAPH POLYTOPE

Authors
TALLURI KT WAGNER DK
Citation
Kt. Talluri et Dk. Wagner, ON THE K-CUT SUBGRAPH POLYTOPE, Mathematical programming, 67(1), 1994, pp. 121-132
Citations number
8
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Mathematical programming → ACNP
ISSN journal
00255610
Volume
67
Issue
1
Year of publication
1994
Pages
121 - 132
Database
ISI
SICI code
0025-5610(1994)67:1<121:OTKSP>2.0.ZU;2-E
Abstract
We consider the problem of finding a minimum-cost set of k pairwise-di sjoint (s,t)-cuts in a graph. For non-negative costs, this problem was solved independently by Nishihara and Inoue, and Wagner. Both solutio ns involve formulating the problem as a linear-programming problem. In this paper, we give new polyhedral interpretations of the problem. Re lationships to the path formulation of the maximum-flow problem are al so established.