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:

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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2013},
NUMBER = {TR-2013-06}

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