All-to-all Broadcast Problems on Cartesian Product Graphs
| Autor: | Jen-Chun Lin, 林仁俊 |
|---|---|
| Rok vydání: | 2013 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 101 All-to-all communication occurs in many important applications in parallel processing. In this thesis, 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 Q2n under this model. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|