Premium
Independent spanning trees on folded hyper‐stars
Author(s) -
Yang JinnShyong,
Chang JouMing
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20389
Subject(s) - hypercube , stars , star (game theory) , spanning tree , computer science , broadcasting (networking) , combinatorics , fault tolerance , degree (music) , class (philosophy) , interconnection , extension (predicate logic) , mathematics , discrete mathematics , computer network , distributed computing , physics , artificial intelligence , mathematical analysis , acoustics , computer vision , programming language
Fault‐tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple independent spanning trees (ISTs) as a broadcasting scheme or a distribution protocol for receiving high levels of fault‐tolerance and security. Recently, hyper‐stars were introduced as a competitive model of interconnection network for both hypercubes and star graphs. The class of folded hyper‐stars is a strengthened variation of hyper‐stars obtained by adding additional links to connect complemented nodes. Both hyper‐stars and folded hyper‐stars have been shown to have lower network cost (measured by the product of degree and diameter) than hypercubes, folded hypercubes, and other variants. In this article, we propose an algorithm to construct k + 1 ISTs on a regular folded hyper‐star FHS (2 k , k ), where the number of ISTs matches the connectivity of FHS(2 k , k ). In particular, for k > 4, the constructed k ISTs have height 2 k − 2, and the other one has height k + 1. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010