direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 30-2008

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
On the dominant of the s-t-cut polytope
Authors
Martin Skutella and Alexia Weber
Publication
Submitted.
Classification
not available
Keywords
flows, cuts, polyhedral combinatorics
Abstract
The natural linear programming formulation of the maximum s-t-flow problem in path-variables has a dual linear program whose underlying polyhedron is the dominant of the s-t-cut polytope. We present a complete characterization of this polyhedron with respect to vertices, facets, and adjacency.
Source
Download as [PDF]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe