TR-2003-09

On polyhedra related to even factors

Tamás Király, Márton Makai

Published in:
Proc. 10th International Conferenference IPCO 2004, LNCS 3064 (2004), 416-430.

As a common generalization of matchings and matroid intersection, W.H. Cunningham and J.F. Geelen introduced the notion of path-matching, which they generalized even further by introducing even factors of weakly symmetric digraphs. Later, a purely combinatorial approach to even factors was given by Gy. Pap and L. Szego, who showed that the maximum even factor problem remains tractable in the class of hardly symmetric digraphs. The present paper shows a direct polyhedral way to derive weighted integer min-max formulae generalizing those previous results.

Bibtex entry:

@techreport{egres-03-09,

AUTHOR	=	{Kir{\'a}ly, Tam{\'a}s and Makai, M{\'a}rton},
TITLE	=	{On polyhedra related to even factors},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2003},
NUMBER	=	{TR-2003-09}

}