|
Generalizing path-matchings, W.H. Cunningham and J.F. Geelen introduced the notion of even factor in directed graphs. In weakly symmetric directed graphs they proved a min-max formula for the maximum cardinality even factor by algebraic method and also discussed a primal-dual method for the weighted case. Later, Gy. Pap and L. Szego proved a simplified formula by purely combinatorial method and derived a Gallai-Edmonds type structure theorem. In this paper, polyhedra related to even factors are considered, integrality and total dual integrality of these linear descriptions are proved directly, without using earlier unweighted results.
Bibtex entry:
| AUTHOR | = | {Makai, M{\'a}rton}, |
| TITLE | = | {A polyhedral approach to even factors}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2003}, |
| NUMBER | = | {TR-2003-05} |