A MESSAGE-ROUTING STRATEGY FOR MULTICOMPUTER SYSTEMS

被引：3

作者：

CHOI, HA ^{[1
]}

ESFAHANIAN, AH ^{[1
]}

机构：

[1] MICHIGAN STATE UNIV,DEPT COMP SCI,E LANSING,MI 48824

来源：

NETWORKS | 1992年 / 22卷 / 07期

关键词：

D O I：

10.1002/net.3230220703

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 [计算机科学与技术];

摘要：

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.

引用

页码：627 / 646

页数：20

共 23 条

[1]

ROUTING TO MULTIPLE DESTINATIONS IN COMPUTER-NETWORKS [J].