Premium
A message‐routing strategy for multicomputer systems
Author(s) -
Choi HyeongAh,
Esfahanian AbdolHossein
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220703
Subject(s) - computer science , hypercube , heuristics , graph , routing (electronic design automation) , parallel computing , theoretical computer science , distributed computing , computer network , operating system
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.