New Developments in Arborescence Packing Problems

本文研究了有向图的基本问题之一-树形填充问题。我们的主要结果可以描述如下。第一个问题是弧不相交树形图根定位问题的多项式时间可解性和难解性。第二个是弧不相交树形图的极大极小定理的加权形式。最后一个算法是利用DM分解求解与树形填充有关的带优先级约束的拟阵求交问题。

In this research, we studied arborescence packing problems that is one of fundamental problems in directed graphs. Our main results can be described as follows. The first one is the polynomial-time solvability and intractability of the root location problem for arc-disjoint arborescences. The second one is the weighted version of the min-max theorem for arc-disjoint arborescences. The last one is the algorithm using a DM decomposition for the matroid intersection problem with priority constraints that is related to packing arborescences.