A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts

DOI10.1007/BF01585926zbMath0845.90047OpenAlexW1997781543MaRDI QIDQ1904657

Naveen Garg, Vijay V. Vazirani

Publication date: 1 February 1996

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585926

zbMATH Keywords

polyhedral combinatoricsmaximum \(s- t\) flow problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Deterministic network models in operations research (90B10)

Related Items

On the dominant of the \(s\)-\(t\)-cut polytope: vertices, facets, and adjacency, On the minimum \(s-t\) cut problem with budget constraints, The negative cycles polyhedron and hardness of checking some polyhedral properties

Cites Work

• Maximal Flow Through a Network
• On Linear Characterizations of Combinatorial Optimization Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item