All-to-all broadcast problems on Cartesian product graphs

Fei Huang Chang, Ma Lian Chia, David Kuo, Sheng Chyang Liaw, Jen Chun Ling

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 Q2n under this model.

Original languageEnglish
Pages (from-to)262-271
Number of pages10
JournalTheoretical Computer Science
StatePublished - 4 Jan 2016


  • All-to-all broadcast
  • All-to-all broadcasting number
  • Broadcasting set
  • Cartesian product
  • Complete graph
  • Cycle
  • Hypercube


Dive into the research topics of 'All-to-all broadcast problems on Cartesian product graphs'. Together they form a unique fingerprint.

Cite this