Back to search
University of Waterloo
Single Commodity Flow Algorithms for Lifts of Graphic and Cographic Matroids
Abstract
dc:description.abstractConsider 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.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2013
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Stuive, Leanne
Subjects
dc:subject × 2Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/7225