Constructing Three Completely Independent Spanning Trees in Locally Twisted Cubes
In: Frontiers in Algorithmics ISBN: 9783030181253 FAW; (2019)
Online
unknown
Zugriff:
For the underlying graph G of a network, k spanning trees of G are called completely independent spanning trees (CISTs for short) if they are mutually inner-node-disjoint. It has been known that determining the existence of k CISTs in a graph is an NP-hard problem, even for \(k=2\). Accordingly, researches focused on the problem of constructing multiple CISTs in some famous networks. Pai and Chang [28] proposed a unified approach to recursively construct two CISTs with diameter \(2n-1\) in several n-dimensional hypercube-variant networks for \(n\geqslant 4\), including locally twisted cubes \(LTQ_n\). Later on, they provided a new construction for \(LTQ_n\) and showed that the diameter of two CISTs can be reduced to \(2n-2\) if \(n=4\) (and thus is optimal) and \(2n-3\) if \(n\geqslant 5\). In this paper, we intend to construct more CISTs of \(LTQ_n\). We develop a novel tree searching algorithm, called two-stages tree-searching algorithm, to construct three CISTs of \(LTQ_6\) and show that the three CISTs of the high-dimensional \(LTQ_n\) for \(n\geqslant 7\) can be constructed by recursion. The diameters of three CISTs for \(LTQ_n\) we constructed are 9, 12 and 14 when \(n=6\), and are \(2n-3\), \(2n-1\) and \(2n+1\) when \(n\geqslant 7\).
Titel: |
Constructing Three Completely Independent Spanning Trees in Locally Twisted Cubes
|
---|---|
Autor/in / Beteiligte Person: | Chang, Jou-Ming ; Chang, Ruay-Shiung ; Pai, Kung-Jui ; Wu, Ro-Yu |
Link: | |
Quelle: | Frontiers in Algorithmics ISBN: 9783030181253 FAW; (2019) |
Veröffentlichung: | Springer International Publishing, 2019 |
Medientyp: | unknown |
ISBN: | 978-3-030-18125-3 (print) |
DOI: | 10.1007/978-3-030-18126-0_8 |
Schlagwort: |
|
Sonstiges: |
|