Dimensional-permutation-based independent spanning trees in bijective connection networks

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

15 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number6747363
Pages (from-to)45-53
Journal / PublicationIEEE Transactions on Parallel and Distributed Systems
Volume26
Issue number1
Publication statusPublished - 1 Jan 2015

Abstract

In recent years, there are many new findings on independent spanning trees (ISTs for short) in hypercubes, crossed cubes, locally twisted cubes, and Möbius cubes, which all belong to a more general network category called bijective connection networks (BC networks). However, little progress has been made for ISTs in general BC networks. In this paper, we first propose the definitions of conditional BC networks and V-dimensional-permutation. We then give a linear parallel algorithm of ISTs rooted at an arbitrary vertex in conditional BC networks, which include hypercubes, crossed cubes, locally twisted cubes, and Möbius cubes, based on the ascending circular dimensional-permutation, where the ISTs are all isomorphic to the binomial-like tree. In addition, we show that there exists an efficient algorithm to construct a spanning tree rooted at an arbitrary vertex in any BC network Xn , and all V-dimensional-permutations can be used to construct spanning trees isomorphic to the n-level binomial tree and rooted at an arbitrary vertex in Xn.

Research Area(s)

  • Bijective connection network, binomial tree, dimensional-permutation, independent spanning trees, reliable broadcasting