On maximal independent arborescence-packing

Csaba Király

Published in:
SIAM J. Discrete Math., 30(4), 2107–2114. DOI link


In this paper, we generalize the results of Kamiyama, Katoh and Takizawa to solve the following problem. Given a digraph $D=(V,A)$ and a matroid on an abstract set $S=\{s_1,...,s_k\}$ along with a map $\pi:S\to V$; give $k$ edge-disjoint arborescences $T_1,..., T_k$ with roots $\pi(s_1),...,\pi(s_k)$ such that for any $v\in V$ the set $\{s_i:v\in T_i\}$ is independent and its rank reaches the theoretical maximum. We also give a simplified proof for the result of Fujishige from the result of Kamiyama et al.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Csaba},
TITLE = {On maximal independent arborescence-packing},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2013},
NUMBER = {TR-2013-03}

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