Balanced spanning trees in complete and incomplete star graphs
Authors:
- Tzung-Shi ChenTCTzung-Shi Chen
- Yu-Chee TsengYTYu-Chee Tseng
- Jang-Ping SheuJSJang-Ping Sheu
- 1 July 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 7 (7) , 717-723
Abstract
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 paperKeywords
This publication has 9 references indexed in Scilit:
- An optimal broadcasting algorithm without message redundancy in star graphsIEEE Transactions on Parallel and Distributed Systems, 1995
- Communication aspects of the star graph interconnection networkIEEE Transactions on Parallel and Distributed Systems, 1994
- A comparative study of topological properties of hypercubes and star graphsIEEE Transactions on Parallel and Distributed Systems, 1994
- Incomplete star: an incrementally scalable network based on the star graphIEEE Transactions on Parallel and Distributed Systems, 1994
- A broadcasting algorithm in star graph interconnection networksInformation Processing Letters, 1993
- The 4-star graph is not a subgraph of any hypercubeInformation Processing Letters, 1993
- Optimal broadcasting on the star graphIEEE Transactions on Parallel and Distributed Systems, 1992
- Data communication and computational geometry on the star and pancake interconnection networks1991
- Optimum broadcasting and personalized communication in hypercubesIEEE Transactions on Computers, 1989