Back to Search
Start Over
All-to-all broadcast problems on Cartesian product graphs.
- Source :
-
Theoretical Computer Science . Jan2016 Part 1, Vol. 609, p262-271. 10p. - Publication Year :
- 2016
-
Abstract
- All-to-all communication occurs in many important applications in parallel processing. In this paper, we study the all-to-all broadcast number (the shortest time needed to complete the all-to-all broadcast) of Cartesian product of graphs under the assumption that: each vertex can use all of its links at the same time, and each communication link is half duplex and can carry only one message at a unit of time. We give upper and lower bounds for the all-to-all broadcast number of Cartesian product of graphs and give formulas for the all-to-all broadcast numbers of some classes of graphs, such as the Cartesian product of two cycles, the Cartesian product of a cycle with a complete graph of odd order, the Cartesian product of two complete graphs of odd order, and the hypercube Q 2 n under this model. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 609
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 111184241
- Full Text :
- https://doi.org/10.1016/j.tcs.2015.10.002