A polyhedron with alls—t cuts as vertices,and adjacency of cuts |
| |
Authors: | Naveen Garg Vijay V. Vazirani |
| |
Affiliation: | (1) Max Planck Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, Germany;(2) College of Computing, Georgia Institute of Technology, Atlanta, GA, USA |
| |
Abstract: | Consider the polyhedron represented by the dual of the LP formulation of the maximums–t flow problem. It is well known that the vertices of this polyhedron are integral, and can be viewed ass–t cuts in the given graph. In this paper we show that not alls–t cuts appear as vertices, and we give a characterization. We also characterize pairs of cuts that form edges of this polyhedron. Finally, we show a set of inequalities such that the corresponding polyhedron has as its vertices alls–t cuts.Work done at the Department of Computer Science and Engineering, Indian Institute of Technology, Delhi, India. |
| |
Keywords: | Flow Cuts Polyhedral combinatorics |
本文献已被 SpringerLink 等数据库收录! |
|