1. All-to-all broadcast problems on Cartesian product graphs.
- Author
-
Chang, Fei-Huang, Chia, Ma-Lian, Kuo, David, Liaw, Sheng-Chyang, and Ling, Jen-Chun
- Subjects
- *
COMPLETE graphs , *CARTESIAN coordinates , *PARALLEL processing , *GEOMETRIC vertices , *MATHEMATICAL bounds , *PATHS & cycles in graph theory - 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]
- Published
- 2016
- Full Text
- View/download PDF