Fortier et al. proposed several research problems on packing arborescences. Some of them were settled in that article and others were solved later by Matsuoka and Tanigawa and by Gao and Yang. The last open problem is settled in this article. We show how to turn an inductive idea used in the latter two articles into a simple proof technique that allows to relate previous results on arborescence packings. We show how a strong version of Edmonds' theorem on packing spanning arborescences implies Kamiyama, Katoh and Takizawa's result on packing reachability arborescences and how Durand de Gevigney, Nguyen and Szigeti's theorem on matroid-based packing of arborescences implies Kir\'aly's result on matroid-reachability-based packing of arborescences. Finally, we deduce a new result on matroid-reachability-based packing of mixed hyperarborescences from a theorem on matroid-based packing of mixed hyperarborescences due to Fortier et al.. In the last part of the article, we deal with the algorithmic aspects of the problems considered. We first obtain algorithms to find the desired packings of arborescences in all settings and then apply Edmonds' weighted matroid intersection algorithm to also find solutions minimizing a given weight function.
翻译:Fortier et al. 提议了有关包装芳香的几项研究问题。 其中一些问题已在文章中解决, 另一些问题后来由松冈、 谷川谷川和高阳解决了。 最后一个公开的问题在文章中解决了。 我们展示了如何将后两篇文章中使用的诱导思想转化为简单的证明技术, 从而可以将先前关于食欲包装的结果联系起来。 我们展示了Edmonds关于跨越过敏量包装的强烈版本意味着Kamiyama、Katoh和Takizazawa关于包装易达标重量的结果,以及Durand de Gevigney、Nguyen和Szigeti关于以甲醇为基础的包装的理论如何在Arboresces包装中意味着Kir\'aly的结果。 我们展示了Edmonds关于覆盖过敏度包装的基于甲状腺的金- 、 Katoh 和Takizzazazao的混合超博林包装方法的新结果, 也考虑到了基于以机类包装为基础的混合超高博博质包装中, 以及最终的算算法问题。