A polyhedron with alls-t cuts as vertices and adjacency of cuts

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