Small Min-Cut Polyhedra
Author:
- 1 February 1999
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 24 (1) , 35-49
Abstract
We study small min-cut polyhedra for directed and undirected complete graphs. We give the ideal descriptions of the polyhedra for undirected graphs with up to seven nodes and for directed graphs with up to five nodes, and generalize the inequalities for complete graphs with arbitrary number of nodes. The facial structure of the polyhedra turns out to be unexpectedly rich.Keywords
This publication has 10 references indexed in Scilit:
- Implementing an efficient minimum capacity cut algorithmMathematical Programming, 1994
- Geometric Algorithms and Combinatorial Optimization1993
- A complete description of the traveling salesman polytope on 8 nodesOperations Research Letters, 1991
- Small Travelling Salesman PolytopesMathematics of Operations Research, 1991
- An efficient algorithm for the minimum capacity cut problemMathematical Programming, 1990
- The facets of the asymmetric 5-city traveling salesman polytopeMathematical Methods of Operations Research, 1989
- On the cut polytopeMathematical Programming, 1986
- The complexity of facets (and some facets of complexity)Journal of Computer and System Sciences, 1984
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981
- Multi-Terminal Network FlowsJournal of the Society for Industrial and Applied Mathematics, 1961