TR-2013-06

Covering intersecting bi-set families under matroid constraints

Kristóf Bérczi, Tamás Király, Yusuke Kobayashi

Edmonds' fundamental theorem on arborescences characterizes the existence of k pairwise edge-disjoint arborescences with the same root in a directed graph. Lovász gave an elegant alternative proof which became the base of many extensions of Edmonds' result.
 
In this paper, we use a modification of Lovász' method to prove a theorem on covering intersecting bi-set families under matroid constraints. Our result can be considered as a common generalization of previous results on packing arborescences.

Bibtex entry:

@techreport{egres-13-06,

AUTHOR	=	{B{\'e}rczi, Krist{\'o}f and Kir{\'a}ly, Tam{\'a}s and Kobayashi, Yusuke},
TITLE	=	{Covering intersecting bi-set families under matroid constraints},
NOTE	=	{{\tt www.cs.elte.hu/egres}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2013},
NUMBER	=	{TR-2013-06}

}