Matroid-Based Packing of Arborescences
Olivier Durand de Gevigney, Viet-Hang Nguyen, Zoltán Szigeti
Source abstract
We provide the directed counterpart of a slight extension of Katoh and Tanigawa's result [SIAM J. Discrete Math., 27 (2013), pp. 155--185] on rooted-tree decompositions with matroid constraints. Our result characterizes digraphs having a packing of arborescences with matroid constraints. It is a proper extension of Edmonds' result [Combinatorial Algorithms, Algorithmics Press, New York, 1973] on packing of spanning arborescences and implies---using a general orientation result of Frank [J. Combin. Theory Ser. B, 28 (1980), pp. 251--261]---the above result of Katoh and Tanigawa. We also give a complete description of the convex hull of the incidence vectors of the matroid-based packings of arborescences and prove that the minimum cost version of the problem can be solved in polynomial time.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.