.png){kind=icon}
返回
Natural cycletrees: Flexible interconnection graphs
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.1996.0023.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Natural cycletrees, formally defined in this paper, is a subclass of Hamiltonian graphs with maximum degree 3 that contain a binary spanning tree. A natural cycletree used as an interconnection network thus supports directly broadcasting through the binary tree as well as nearest-neighbor communication through the cycle. Natural cycletrees have several other interesting properties; e.g., they are planar, easily extensible, and can be contracted using the same methods as for binary trees. The main results of the paper are: (i) Given an arbitrary basic binary spanning tree T, there exists a natural cycletree with a minimal number of edges for T. (ii) A natural cycletree has a very simple router. We give a superfast parallel algorithm that can establish near optimal router data for that router. (C) 1996 Academic Press, Inc.
Keyword:
NETWORK
VLSI
