.png){kind=icon}
返回
A Fast Parallel Algorithm for Constructing Independent Spanning Trees on Parity Cubes
.png){kind=icon}
PRE
AI
DOI：10.1016/j.amc.2015.06.081.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Zehavi and Itai (1989) proposed the following conjecture: every k-connected graph has k in dependent spanning trees (ISTs for short) rooted at an arbitrary node. An n-dimensional parity cube, denoted by PQ(n), is a variation of hypercubes with connectivity: and has many features superior to those of hypercubes. Recently, Wang et al. (2012) confirmed the ISTs conjecture by providing an O(N log N)algorithm to construct n ISTs rooted at an arbitrary node on PQ(n), where N - 2(n) is the number of nodes in PQ(n). 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 PQ(n) in O(log N) time using N processors. In particular, the constructing rule of spanning trees is simple and the proof of independency is easier than ever before. (C) 2015 Elsevier Inc. All rights reserved.
Keyword:
Parallel algorithms
Independent spanning trees
Parity cubes
Interconnection networks
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.4
论文数:
2.3W
被引数:
3.3W
机构
引用论文
In vivo voltammetric evidence that locus coeruleus activation predominantly releases norepinephrine in the infralimbic cortex: Effect of acute ethanol.png)
Synapse
SynapseIF0
PREAI
分享收藏分享收藏Stepwise sliding disintegration of tetrahymena ciliary axonemes at higher concentrations of ATP
PREAI
分享收藏The physiological role of ADP and Mg2+ in maintaining a stable beat cycle in bull spermCytoskeleton
CytoskeletonIF0
PREAI
分享收藏Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes
PREAI
分享收藏
查看更多内容