On Reachability Mixed Arborescence Packing
On Reachability Mixed Arborescence Packing
复制标题
DOI：
10.1016/j.disopt.2018.10.002
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
Tatsuya Matsuoka;Shin-ichi Tanigawa
中科院分区：
文献类型：
--
作者：
Tatsuya Matsuoka;Shin-ichi Tanigawa
作为Edmonds树形填充定理的推广，Kamiyama-Katoh-Takizawa（2009）给出了包含从每个根可达的顶点集的弧不相交树形的有向图的一个很好的刻画。Fortier-Király-Léonard-Szigeti-Talon（2018）提出了一个问题，即这个结果是否可以通过允许有向弧和无向边来扩展到混合图。在本文中，我们解决了这个问题，通过开发一个多项式时间的算法，找到一个收集的边和弧不相交的树形图，从每个根在一个给定的混合图可达的顶点集。
As a generalization of Edmonds’ arborescence packing theorem, Kamiyama–Katoh–Takizawa (2009) provided a good characterization of directed graphs that contain arc-disjoint arborescences spanning the set of vertices reachable from each root. Fortier–Király–Léonard–Szigeti–Talon (2018) asked whether the result can be extended to mixed graphs by allowing both directed arcs and undirected edges. In this paper, we solve this question by developing a polynomial-time algorithm for finding a collection of edge and arc-disjoint arborescences spanning the set of vertices reachable from each root in a given mixed graph.