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

作者：

Highlights：

• 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.

摘要

•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.

论文关键词：Parallel algorithms,Independent spanning trees,Parity cubes,Interconnection networks

论文评审过程：Received 18 September 2014, Revised 24 May 2015, Accepted 13 June 2015, Available online 14 July 2015, Version of Record 14 July 2015.

论文官网地址：https://doi.org/10.1016/j.amc.2015.06.081