Balanced spanning trees in complete and incomplete star graphs
- 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
- https://doi.org/10.1109/71.508251
Abstract
[[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 paper.[[fileno]]2030224010014[[department]]資訊工程學Keywords
This publication has 10 references indexed in Scilit:
- Embedding of cycles and grids in star graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- 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 networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1991
- Optimum broadcasting and personalized communication in hypercubesIEEE Transactions on Computers, 1989