PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 3 | 427-437
Tytuł artykułu

Completely Independent Spanning Trees in (Partial) k-Trees

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
35
Numer
3
Strony
427-437
Opis fizyczny
Daty
wydano
2015-08-01
otrzymano
2014-04-24
poprawiono
2014-08-08
zaakceptowano
2014-08-08
online
2015-07-29
Twórcy
  • Department of Computer Science Gunma University, Kiryu Gunma 376-8515 Japan, otachi@jaist.ac.jp
autor
  • School of Information Science Japan Advanced Institute of Science and Technology Asahidai 1-1, Nomi, Ishikawa 923-1292, Japan, otachi@jaist.ac.jp
autor
  • 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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1806
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.