TR-2004-01

On factorizations of directed graphs by cycles

Gyula Pap, László Szegő



Abstract

In this paper we present a min-max theorem for a factorization problem in directed graphs. This extends the Berge-Tutte formula on matchings as well as formulas for the maximum even factor in weakly symmetric directed graphs and a factorization problem in undirected graphs. We also prove an extension to the structural theorem of Gallai and Edmonds about a canonical set attaining minimum in the formula. The matching matroid can be generalized to this context: we get a matroidal description of the coverable node sets.


Bibtex entry:

@techreport{egres-04-01,
AUTHOR = {Pap, Gyula and Szeg{\H o}, L{\'a}szl{\'o}},
TITLE = {On factorizations of directed graphs by cycles},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2004},
NUMBER = {TR-2004-01}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!