A Fast Parallel Algorithm for Constructing Independent Spanning Trees on Parity Cubes

• We study the independent spanning trees (IST) problem on parity cubes PQn.
• We present a non-recursive scheme for constructing n ISTs in PQn.
• The algorithm can be parallelized to run in O(n) time using 2n processors.

Zehavi and Itai (1989) proposed the following conjecture: every k-connected graph has k independent spanning trees (ISTs for short) rooted at an arbitrary node. An n-dimensional parity cube, denoted by PQn, is a variation of hypercubes with connectivity n   and has many features superior to those of hypercubes. Recently, Wang et al. (2012) confirmed the ISTs conjecture by providing an O(NlogN)O(NlogN) algorithm to construct n ISTs rooted at an arbitrary node on PQn  , where N=n2N=2n is the number of nodes in PQn. However, this algorithm is executed in a recursive fashion and thus is hard to be parallelized. In this paper, we present a non-recursive and fully parallelized approach to construct n ISTs rooted at an arbitrary node of PQn   in O(logN)O(logN) time using N processors. In particular, the constructing rule of spanning trees is simple and the proof of independency is easier than ever before.