论文标题
树木包装中的可达性
Reachability in arborescence packings
论文作者
论文摘要
Fortier等。提出了一些有关包装树木的研究问题。他们中的一些人在那篇文章中解决了，其中一些人后来由Matsuoka和Tanigawa以及Gao和Yang解决。本文解决了最后一个开放问题。我们展示了如何将后两篇文章中使用的归纳想法变成一种简单的证明技术，该技术允许将先前的树木包装结果联系起来。 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ály's result on matroid-reachability-based packing of arborescences. 最后，我们从基于Fortier等人的混合高甲状腺填料定理中推断出基于原子质的高碳酸盐填料的基于原始的高碳酸盐填料的新结果。 在本文的最后一部分中，我们处理了所考虑的问题的算法方面。我们首先获取算法，以在所有设置中找到所需的植弧包装，然后应用Edmonds加权的Matroid相交算法，以找到最小化给定重量函数的解决方案。
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ály'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.
