Reachability in arborescence packings (Q2166224)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reachability in arborescence packings |
scientific article |
Statements
Reachability in arborescence packings (English)
0 references
24 August 2022
0 references
The authors consider the packing of arborescences in this paper. First, they show how to translate the inductive concepts used in the latter two articles into a simple proof technique that allows for associating previous results on arborescence packings. Second, they verify that a strong version of Edmunds' theorem on packing spanning arborescences implies \textit{N. Kamiyama} et al.'s result on packing reachability arborescences [Combinatorica 29, No. 2, 197--214 (2009; Zbl 1212.05209)] and that \textit{O. D. de Gevigney} et al.'s theorem on matroid-based packing of arborescences [SIAM J. Discrete Math. 27, No. 1, 567--574 (2013; Zbl 1268.05165)] implies \textit{C. Király}'s result on matroid-reachability-based packing of arborescences [SIAM J. Discrete Math. 30, No. 4, 2107--2114 (2016; Zbl 1350.05138)]. Third, they infer a new result about matroid-reachability-based packing of mixed hyperarborescences from a theorem on matroid-based packing of mixed hyperarborescences due to \textit{Q. Fortier} et al. [Discrete Appl. Math. 242, 26--33 (2018; Zbl 1384.05119)]. Finally, they discuss the algorithmic aspects of the problems considered, they derive algorithms to find the desired packings of arborescences in all settings and utilize Edmonds' weighted matroid intersection algorithm to find solutions minimizing a given weight function.
0 references
arborescence
0 references
packing
0 references
matroid
0 references
0 references
0 references