Single Commodity Flow Algorithms for Lifts of Graphic and Cographic Matroids

discrete optimization;matroid flows;Combinatorics and Optimization

Stuive, Leanne

University of Waterloo

关键词: discrete optimization;    matroid flows;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/7225/1/Stuive_Leanne.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Consider a binary matroid M given by its matrix representation. We show that if M is a lift of a graphic or a cographic 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.