2013 | OriginalPaper | Buchkapitel
Single Commodity-Flow Algorithms for Lifts of Graphic and Co-graphic Matroids
verfasst von : Bertrand Guenin, Leanne Stuive
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Consider a binary matroid
M
given by its matrix representation. We show that if
M
is a lift of a graphic or a co-graphic matroid, then in polynomial time we can either solve the single commodity flow problem for
M
or find an obstruction for which the Max-Flow Min-Cut relation does not hold. The key tool is an algorithmic version of Lehman’s Theorem for the set covering polyhedron.