Edmondsu27s fundamental theorem on arborescences in [J. Edmonds, Edge-disjoint branchings, in Combinatorial Algorithms, Courant Comput. Sci. Sympos. 9, Algorithmics Press, New York, 1973, pp. 91--96] characterizes the existence of $k$ pairwise arc-disjoint spanning arborescences with the same root in a directed graph. In [L. Lovász, J. Combinatorial Theory Ser. B, 21 (1976), pp. 96--103], Lovász gave an elegant alternative proof which became the basis of many extensions of Edmondsu27s result. In this paper, we use a modification of Lovászu27s method to prove a theorem on covering intersecting bi-set families under matroid constraints. Our result can be considered as an extension of previous results on packing arborescences. We also investigate the algorithmic aspects of the problem and present a polynomial-time algorithm for solving the corresponding optimization problem.
展开▼
机译：埃德蒙兹（Edmonds）的关于树状化的基本定理[J. Edmonds，边缘不相交的分支，在《组合算法》中，Courant Comput。科学座谈会。 9号算法出版社，纽约，1973年，第91--96页]描述了在有向图中具有相同根的$ k $成对弧不相交跨越树状体的存在。在[L. Lovász，J.组合理论系列。 B，21（1976），pp。96--103]，洛瓦兹给出了一个优雅的替代证明，它成为了埃德蒙兹成绩的许多扩展的基础。在本文中，我们使用Lovász u27s方法的一种改进来证明关于覆盖拟阵约束下的相交双集族的一个定理。我们的结果可以被认为是先前关于包装树状结构结果的扩展。我们还研究了问题的算法方面，并提出了用于解决相应优化问题的多项式时间算法。
展开▼
