EUVIMEDEUVIMED entdecken
Crossref

A Recursive Algorithm for Constructing Dual-CISTs in Hierarchical Folded Cubic Networks

Hsin-Jung Lin, Shyue-Ming Tang, Kung-Jui Pai, Jou-Ming Chang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →