Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes

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

34 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)641-652
Journal / PublicationJournal of Parallel and Distributed Computing
Issue number5
Online published30 Jan 2013
Publication statusPublished - May 2013


Independent spanning trees (ISTs) have increasing applications in fault-tolerance, bandwidth, and security. In this paper, we study the problem of parallel construction of ISTs on crossed cubes. We first propose the definitions of dimension-adjacent walk and dimension-adjacent tree along with a dimension property of crossed cubes. Then, we consider the parallel construction of ISTs on crossed cubes. We show that there exist n general dimension-adjacent trees which are independent of the addresses of vertices in the n-dimensional crossed cube CQn. Based on n dimension-adjacent trees and an arbitrary root vertex, a parallel algorithm with the time complexity O(2n) is proposed to construct n ISTs on CQn, where n ≥ 1.

Research Area(s)

  • Crossed cube, Independent spanning tree, Internally disjoint path, Dimension-adjacent tree, Parallel construction