Completely Independent Spanning Trees in (Partial) k-Trees

• Autorzy: Masayoshi Matsushita , Yota Otachi , Toru Araki
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

completely independent spanning trees; partial k-trees.

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 3
• Strony: 427-437

Daty

wydano

2015-08-01

otrzymano

2014-04-24

poprawiono

2014-08-08

zaakceptowano

2014-08-08

online

2015-07-29

Twórcy

autor

Masayoshi Matsushita

• Department of Computer Science Gunma University, Kiryu Gunma 376-8515 Japan

autor

Yota Otachi

• School of Information Science Japan Advanced Institute of Science and Technology Asahidai 1-1, Nomi, Ishikawa 923-1292, Japan

autor

Toru Araki

• Department of Computer Science Gunma University, Kiryu Gunma 376-8515 Japan

Bibliografia

• [1] T. Araki, Dirac’s condition for completely independent spanning trees, J. Graph Theory 77 (2014) 171-179. doi:10.1002/jgt.21780[WoS][Crossref]
• [2] S. Arnborg and A. Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Appl. Math. 23 (1989) 11-24. doi:10.1016/0166-218X(89)90031-0[Crossref]
• [3] H.L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci. 209 (1998) 1-45. doi:10.1016/S0304-3975(97)00228-4[Crossref]
• [4] H.L. Bodlaender, F.V. Fomin, P.A. Golovach, Y. Otachi and E.J. van Leeuwen, Parameterized complexity of the spanning tree congestion problem, Algorithmica 64 (2012) 85-111. doi:10.1007/s00453-011-9565-7[WoS][Crossref]
• [5] H.L. Bodlaender and A.M.C.A. Koster, Combinatorial optimization on graphs of bounded treewidth, Comput. J. 51 (2008) 255-269. doi:10.1093/comjnl/bxm037 [WoS][Crossref]
• [6] B. Courcelle, The monadic second-order logic of graphs III: tree-decompositions, minors and complexity issues, Theor. Inform. Appl. 26 (1992) 257-286.
• [7] T. Hasunuma, Completely independent spanning trees in the underlying graph of a line digraph, Discrete Math. 234 (2001) 149-157. doi:10.1016/S0012-365X(00)00377-0[Crossref]
• [8] T. Hasunuma, Completely independent spanning trees in maximal planar graphs in: Proceedings of 28th Graph Theoretic Concepts of Computer Science (WG 2002), LNCS 2573, Springer-Verlag Berlin (2002) 235-245. doi:10.1007/3-540-36379-3 21[Crossref]
• [9] T. Hasunuma and C. Morisaka, Completely independent spanning trees in torus networks, Networks 60 (2012) 59-69. doi:10.1002/net.20460[WoS][Crossref]
• [10] P. Hlinĕný, S. Oum, D. Seese and G. Gottlob, Width parameters beyond tree-width and their applications, Comput. J. 51 (2008) 326-362. doi:10.1093/comjnl/bxm052[WoS][Crossref]
• [11] F. Péterfalvi, Two counterexamples on completely independent spanning trees, Dis- crete Math. 312 (2012) 808-810. doi:10.1016/j.disc.2011.11.0 [WoS][Crossref]

Identyfikatory

DOI

10.7151/dmgt.1806