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.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/7225 |
| Date | January 2013 |
| Creators | Stuive, Leanne |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0019 seconds