## 摘要

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_{2n} under this model.

原文 | ???core.languages.en_GB??? |
---|---|

頁（從 - 到） | 262-271 |

頁數 | 10 |

期刊 | Theoretical Computer Science |

卷 | 609 |

DOIs | |

出版狀態 | 已出版 - 4 1月 2016 |