TR-2013-06

Covering intersecting bi-set families under matroid constraints

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



Abstract

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}
}


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