Garg, Naveen ; Vazirani, Vijay V. (1995) A polyhedron with alls-t cuts as vertices and adjacency of cuts Mathematical Programming, 70 (1). pp. 17-25. ISSN 0025-5610
Full text not available from this repository.
Official URL: http://link.springer.com/article/10.1007/BF0158592...
Related URL: http://dx.doi.org/10.1007/BF01585926
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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer Verlag. |
| Keywords: | Flow; Cuts; Polyhedral Combinatorics |
| ID Code: | 101274 |
| Deposited On: | 31 Jan 2018 09:34 |
| Last Modified: | 31 Jan 2018 09:34 |
Repository Staff Only: item control page
