Balanced spanning trees in complete and incomplete star graphs

被引：16

作者：

Chen, TS

Tseng, YC

Sheu, JP

机构：

[1] CHUNG HUA POLYTECH INST,DEPT COMP SCI,HSINCHU 30067,TAIWAN

[2] NATL CENT UNIV,DEPT COMP SCI & INFORMAT ENGN,CHUNGLI 32054,TAIWAN

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1996年 / 7卷 / 07期

关键词：

balanced spanning tree; interconnection network; parallel architecture; personalized broadcast; star graph;

D O I：

10.1109/71.508251

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Efficiently solving the personalized broadcast problem in an interconnection network typically relies on finding an appropriate spanning tree in the network. In this paper, we show how to construct in a complete star graph an asymptotically balanced spanning tree, and in an incomplete star graph a near-balanced spanning tree. In both cases, the tree is shown to have the minimum height. In the literature, this problem has only been considered for the complete star graph, and the constructed tree is about 4/3 times taller than the one proposed in this paper.

引用

页码：717 / 723

页数：7

共 12 条

[1]

Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393

[2]

AKL SG, 1991, 3RD P IEEE S PAR DIS, P415

[3] A COMPARATIVE-STUDY OF TOPOLOGICAL PROPERTIES OF HYPERCUBES AND STAR GRAPHS [J].