A Parallel Algorithm to Construct BISTs on Parity Cubes
Yan Wang, Jianxi Fan, Wenjun Liu, Yuejuan Han · 2015
Independent spanning trees(ISTs) have applications in interconnection networks such as reliable communication protocols, and secure message distribution, etc. In this paper, we use BIST to denote the IST isomorphic to binomial-like tree. We propose an algorithm to construct n BISTs and the algorithm can be parallelized on PQnto run in O(N) time, where N = 2n.