A Characterization of a Family of Independent Arborescences in a Directed Graph with Convex Sets
András Frank, Satoru Fujishige, Naoyuki Kamiyama, Naoki Katoh · Kyoto University Research Information Repository (Kyoto University) · 2009
The problem of finding arc-disjoint arborescences rooted at r or independent arborescences rooted at r which are a vertex-disjoint analogue of arc-disjoint arborescences in a directed graph D=(V, A) with a specified vertex r∈V is very important from not only the theoretical viewpoint but also the practical viewpoint. Recently, Fujishige extended the characterization on arc-disjoint arborescences presented by Edmonds based on the result of Kamiyama et al. In this paper, we prove that the results presented by Whitty and Huck on independent arborescences can be extended in the same manner as Fujishige's extension of Edmonds' theorem on arc-disjoint arborescences.