TR-2013-03

On maximal independent arborescence-packing

Csaba Király



Abstract

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 www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2013},
NUMBER = {TR-2013-03}
}


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