TR-2013-03

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:

@techreport{egres-13-03,

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

}