Skip to main content

Research Repository

Advanced Search

A class of hierarchical graphs as topologies for interconnection networks

Lai, P.-L.; Hsu, H.-C.; Tsai, C.-H.; Stewart, I.A.

A class of hierarchical graphs as topologies for interconnection networks Thumbnail


Authors

P.-L. Lai

H.-C. Hsu

C.-H. Tsai



Abstract

We study some topological and algorithmic properties of a recently defined hierarchical interconnection network, the hierarchical crossed cube HCC(k,n), which draws upon constructions used within the well-known hypercube and also the crossed cube. In particular, we study: the construction of shortest paths between arbitrary vertices in HCC(k,n); the connectivity of HCC(k,n); and one-to-all broadcasts in parallel machines whose underlying topology is HCC(k,n) (with both one-port and multi-port store-and-forward models of communication). Moreover, (some of) our proofs are applicable not just to hierarchical crossed cubes but to hierarchical interconnection networks formed by replacing crossed cubes with other families of interconnection networks. As such, we provide a generic construction with accompanying generic results relating to some topological and algorithmic properties of a wide range of hierarchical interconnection networks.

Citation

Lai, P., Hsu, H., Tsai, C., & Stewart, I. (2010). A class of hierarchical graphs as topologies for interconnection networks. Theoretical Computer Science, 411(31-33), 2912-2924. https://doi.org/10.1016/j.tcs.2010.04.022

Journal Article Type Article
Publication Date Jun 1, 2010
Deposit Date Apr 12, 2010
Publicly Available Date Jun 2, 2010
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 411
Issue 31-33
Pages 2912-2924
DOI https://doi.org/10.1016/j.tcs.2010.04.022
Keywords Interconnection networks, Hierarchical interconnection networks, Crossed cubes.
Publisher URL http://www.dur.ac.uk/i.a.stewart/Papers/HierCrossedCubes.pdf

Files





You might also like



Downloadable Citations