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

Yu-Huei Chang, Jinn-Shyong Yang, Jou-Ming Chang and Yue-Li Wang

Applied Mathematics and Computation, 2015, vol. 268, issue C, 489-495

Abstract: 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) algorithm to construct n ISTs rooted at an arbitrary node on PQn, where N=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) time using N processors. In particular, the constructing rule of spanning trees is simple and the proof of independency is easier than ever before.

Keywords: Parallel algorithms; Independent spanning trees; Parity cubes; Interconnection networks (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300315008620
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:268:y:2015:i:c:p:489-495

DOI: 10.1016/j.amc.2015.06.081

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().