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

DOI10.1007/BF01585926MaRDI QIDQ1904657zbMATH OpenOpenAlexFDO

Authors 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

maximum \(s- t\) flow problempolyhedral combinatorics

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1263276
• On the dominant of the \(s\)-\(t\)-cut polytope: vertices, facets, and adjacency
• scientific article; zbMATH DE number 3952461
• On the k-cut subgraph polytope
• On the cut polyhedron.

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Maximal Flow Through a Network
• On Linear Characterizations of Combinatorial Optimization Problems

Cited in

(4)

• On the dominant of the \(s\)-\(t\)-cut polytope: vertices, facets, and adjacency
• scientific article; zbMATH DE number 1263276 (Why is no real title available?)
• On the minimum \(s-t\) cut problem with budget constraints
• The negative cycles polyhedron and hardness of checking some polyhedral properties

This page was built for publication: A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1904657)