Constructing tri-CISTs in shuffle-cubes

Yu-Han Chen (), Kung-Jui Pai (), Hsin-Jung Lin () and Jou-Ming Chang ()
Additional contact information
Yu-Han Chen: National Taipei University of Business
Kung-Jui Pai: Ming Chi University of Technology
Hsin-Jung Lin: National Taipei University of Business
Jou-Ming Chang: National Taipei University of Business

Journal of Combinatorial Optimization, 2022, vol. 44, issue 5, No 2, 3194-3211

Abstract: Abstract Let $${\mathcal {T}}=\{T_1,T_2,\ldots ,T_k\}$$ T = { T 1 , T 2 , … , T k } be a set of $$k\geqslant 2$$ k ⩾ 2 spanning trees in a graph G. The k spanning trees are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices x and y in any two trees have neither vertex nor edge in common except for x and y. Particularly, $${\mathcal {T}}$$ T is called a dual-CIST (resp. tri-CIST) provided $$k=2$$ k = 2 (resp. $$k=3$$ k = 3 ). From an algorithmic point of view, the problem of finding a dual-CIST in a given graph is known to be NP-hard. For data transmission applications in reliable networks, the existence of a dual-CIST can provide a configuration of fault-tolerant routing called protection routing. The presence of a tri-CIST can enhance the dependability of transmission and carry out secure message distribution for confidentiality. Recently, the construction of a dual-CIST has been proposed in a shuffle-cube $$SQ_n$$ S Q n , which is an innovative hypercube-variant network that possesses both short diameter and connectivity advantages. This paper uses the CIST-partition technique to construct a tri-CIST of $$SQ_6$$ S Q 6 , and shows that the diameters of three CISTs are 22, 22, and 13. Then, by the hierarchical structure of $$SQ_n$$ S Q n , we propose a recursive algorithm for constructing a tri-CIST for high-dimensional shuffle-cubes. When $$n\geqslant 10$$ n ⩾ 10 , the diameters of $$T_i$$ T i , $$i=1,2,3$$ i = 1 , 2 , 3 , we constructed for $$SQ_n$$ S Q n are as follows: $$2n+11$$ 2 n + 11 , $$2n+9$$ 2 n + 9 , and $$2n+1$$ 2 n + 1 .

Keywords: Completely independent spanning trees; Interconnection networks; Shuffle-cubes; Dual-CISTs; Tri-CISTs; Fault-tolerant routing (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00863-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:5:d:10.1007_s10878-022-00863-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00863-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().