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.