Back to Search
Start Over
A Recursive Algorithm for Constructing Dual-CISTs in Hierarchical Folded Cubic Networks.
- Source :
-
International Journal of Foundations of Computer Science . Aug2024, Vol. 35 Issue 5, p535-550. 16p. - Publication Year :
- 2024
-
Abstract
- Let = { T 1 , T 2 , ... , T k } be a set of 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, is called a dual-CIST provided k = 2. For data transmission applications in reliable networks, the existence of a dual-CIST can provide a configuration of fault-tolerant routing called protection routing. This paper investigates the problem of constructing a dual-CIST in the n -dimensional hierarchical folded cubic network H F Q n . The network is a two-level network using folded hypercube F Q n as clusters to reduce the diameter, hardware overhead and improve the fault tolerance ability. We propose a recursive algorithm to construct a dual-CIST of H F Q n in (2 2 n) time for n ≥ 2 , where the time required is the same scale as the number of vertices of H F Q n . Also, the diameter of each constructed CIST is 4 n + 1. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 35
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 178313978
- Full Text :
- https://doi.org/10.1142/S0129054123500156