Independent spanning trees in crossed cubes

• Our algorithm generates n ISTs for an n-dimensional crossed cube.
• This algorithm runs in time O(NlogN), where N=2nN=2n is the number of the nodes in CQnCQn.
• Our algorithm can be parallelized easily.

This paper addresses the independent spanning trees (ISTs) problem in crossed cubes. The algorithm proposed in this paper generates n ISTs for an n  -dimensional crossed cube (CQnCQn). This algorithm takes time O(NlogN) and can be parallelized to run in time O(logN), where N=2nN=2n is the number of the nodes in CQnCQn. To the best of our knowledge, this is the first algorithm which can parallelly construct the ISTs in crossed cubes.