A Recursive Algorithm for Constructing Dual-CISTs in Hierarchical Folded Cubic Networks
International Journal of Foundations of Computer Science · 2024-08 · 35 (05) · 535-550
DOI: 10.1142/s0129054123500156 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Foundations of Computer Science, online erschienen am 29.08.2023. Verfasst von Hsin-Jung Lin und 3 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 46 Literaturangaben. Gefördert von: Ministry of Science and Technology, Taiwan.
Abstract (Originalsprache)
Let [Formula: see text] be a set of [Formula: see text] spanning trees in a graph [Formula: see text]. The [Formula: see text] spanning trees are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices [Formula: see text] and [Formula: see text] in any two trees have neither vertex nor edge in common except for [Formula: see text] and [Formula: see text]. Particularly, [Formula: see text] is called a dual-CIST provided [Formula: see text]. 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 [Formula: see text]-dimensional hierarchical folded cubic network [Formula: see text]. The network is a two-level network using folded hypercube [Formula: see text] 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 [Formula: see text] in [Formula: see text] time for [Formula: see text], where the time required is the same scale as the number of vertices of [Formula: see text]. Also, the diameter of each constructed CIST is [Formula: see text].
Förderung
- Ministry of Science and Technology, Taiwan
Zitieren
APA
Lin, H., Tang, S., Pai, K., & Chang, J. (2024). A Recursive Algorithm for Constructing Dual-CISTs in Hierarchical Folded Cubic Networks. International Journal of Foundations of Computer Science, 35(05), 535-550. https://doi.org/10.1142/s0129054123500156
Vancouver
Lin H, Tang S, Pai K, Chang J. A Recursive Algorithm for Constructing Dual-CISTs in Hierarchical Folded Cubic Networks. International Journal of Foundations of Computer Science. 2024;35(05):535-550. doi:10.1142/s0129054123500156
BibTeX
@article{Lin2024,
author = {Lin, Hsin-Jung and Tang, Shyue-Ming and Pai, Kung-Jui and Chang, Jou-Ming},
title = {A Recursive Algorithm for Constructing Dual-CISTs in Hierarchical Folded Cubic Networks},
journal = {International Journal of Foundations of Computer Science},
year = {2024},
volume = {35},
number = {05},
pages = {535--550},
doi = {10.1142/s0129054123500156}
}
EUVIMED