Balanced spanning trees in complete and incomplete star graphs

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > journal & Dissertation > Item 987654321/29212

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/29212

Title:	Balanced spanning trees in complete and incomplete star graphs
Authors:	Chen,TS;Tseng,YC;Sheu,JP
Contributors:	資訊工程研究所
Keywords:	BROADCASTING ALGORITHM;COMMUNICATION;HYPERCUBES;NETWORK
Date:	1996
Issue Date:	2010-06-29 20:16:30 (UTC+8)
Publisher:	中央大學
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.
Relation:	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	483	View/Open

社群 sharing