All-to-all broadcast problem of some classes of graphs under the half duplex all-port model

作者：Chang Fei Huang; Chen Young Ming; Chia Ma Lian; Kuo David^*; Yu Ming fen

来源：Discrete Applied Mathematics, 2014, 173: 28-34.

DOI：10.1016/j.dam.2014.03.014

• All-to-all broadcast
• Broadcasting set
• All-to-all broadcast number
• Tree
• Complete bipartite graph
• Double loop network

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 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 graphs and give formulas for the all-to-all broadcast number of trees, complete bipartite graphs and double loop networks under this model.

• 出版日期2014-8-20
• 单位东华大学