An Optimal Broadcasting Algorithm without Message Redundancy in Star Graphs

Jang-Ping Sheu; Chao-Tsung Wu; Tzung-Shi Chen

doi:10.1109/71.388046

Back

An Optimal Broadcasting Algorithm without Message Redundancy in Star Graphs

Journal article

Peer reviewed

An Optimal Broadcasting Algorithm without Message Redundancy in Star Graphs

Jang-Ping Sheu, Chao-Tsung Wu and Tzung-Shi Chen

IEEE Transactions on Parallel and Distributed Systems, Vol.6(6), pp.653-658

1995

DOI: https://doi.org/10.1109/71.388046

Abstract

Broadcasting

interconnection networks

star graphs

Based on the Mendia and Sarkars algorithm [8], we propose an optimal and nonredundant distributed broadcasting algorithm in star graphs. For an n-dimensional star graph, our algorithm takes O(n log2 n) time and guarantees that all nodes in the star graph receive the message exactly once. Moreover, broadcasting m packets in a pipeline fashion takes O(m log2 n + n log2 n) time due to the nonredundant property of our broadcasting algorithm. © 1995 IEEE

Metrics

1 Record Views

See more details

Details

Title: An Optimal Broadcasting Algorithm without Message Redundancy in Star Graphs
Creators - without role: Jang-Ping Sheu - Department of Computer Science and Information Engineering, National Central University
Chao-Tsung Wu - National Central University
Tzung-Shi Chen - National Central University
Identifiers: 9957777221506774
Academic Unit: Institute of Communications Engineering, College of Electrical Engineering and Computer Science, National Tsing Hua University
Language: English
Resource Type: Journal article
Publication Details: IEEE Transactions on Parallel and Distributed Systems, Vol.6(6), pp.653-658

An Optimal Broadcasting Algorithm without Message Redundancy in Star Graphs

Abstract

Related links

Metrics

Details

National Tsing Hua University Social media