Completely Independent Spanning Trees in (Partial) k-Trees
Completely Independent Spanning Trees in (Partial) k-Trees
复制标题
DOI：
10.7151/dmgt.1806
复制
发表时间：
2015-08
影响因子：
0.7
通讯作者：
Toru Araki;M. Matsushita;Y. Otachi
中科院分区：
文献类型：
--
作者：
Toru Araki;M. Matsushita;Y. Otachi
如果对于任何两个顶点u和V，则抽象的两个跨度树T1和T2是完全独立的。在本文中完全跨越CIST（g），当G是部分k-tree时，我们就会表明[K/2]≤Cist（G）≤K-1 -tree G.然后我们向任何p∈{[k/2]定理，我们表明有一种线性时代算法，该算法计算部分k-Tree的CIST（G），其中K是固定常数。
Abstract Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree. First we show that [k/2] ≤ cist(G) ≤ k − 1 for any k-tree G. Then we show that for any p ∈ {[k/2], . . . , k − 1}, there exist infinitely many k-trees G such that cist(G) = p. Finally we consider algorithmic aspects for computing cist(G). Using Courcelle’s theorem, we show that there is a linear-time algorithm that computes cist(G) for a partial k-tree, where k is a fixed constant.