A message‐routing strategy for multicomputer systems

A natural communication problem in a multicomputer system, such as the hypercube, is that a processor (called the source) wants to send a message to a number of other processors (destinations). A message‐routing paradigm for such a multidestination communication has been formulated as finding a subgraph called an Optimal Communication Tree (OCT). We prove that the problem of finding an OCT is NP‐hard for the n‐cube graph as well as for a graph whose maximum degree is at most three. Heuristics for finding suboptimal communication trees for the hypercube multicomputer are discussed.