Arc-disjoint in-trees in directed graphs
Arc-disjoint in-trees in directed graphs
复制标题
DOI：
10.1007/s00493-009-2428-z
复制
发表时间：
2008-01
期刊：
影响因子：
1.1
通讯作者：
Naoyuki Kamiyama;N. Katoh;A. Takizawa
中科院分区：
文献类型：
--
作者：
Naoyuki Kamiyama;N. Katoh;A. Takizawa
给定一个具有一组指定顶点的有向图D=(V，A)S={S1，…，Sd}⊆V和一个函数f：S→ℕ其中ℕ表示自然数的集合，我们给出了存在Σi=1df(Si)弧不交的树的一个充要条件，由ti，1，ti，2，…表示，对于每个i=1，…，d使得Ti，1，…，扎根于每一个Ti，横跨可达的顶点。这推广了Edmonds[2]的结果，即对具有指定顶点∈V的有向图D=(V，A)，存在根于其每一个跨V的弧不交的树内的充要条件。此外，我们将Edmonds的填充in-树的另一种刻画推广到我们的情形。
Given a directed graphD= (V,A) with a set ofdspecified verticesS= {s1,…,sd} ⊆Vand a functionf:S→ ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Σi=1df(si) arc-disjoint in-trees denoted byTi,1,Ti,2,…,for everyi= 1,…,dsuch thatTi,1,…,are rooted atsiand eachTi,jspans the vertices from whichsiis reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed graphD=(V,A) with a specified vertexs∈V, there arekarc-disjoint in-trees rooted atseach of which spansV. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case.