OPTIMAL LINEAR BROADCAST

被引：6

作者：

BITAN, S ^{[1
]}

ZAKS, S ^{[1
]}

机构：

[1] TECHNION ISRAEL INST TECHNOL,DEPT COMP SCI,HAIFA,ISRAEL

来源：

JOURNAL OF ALGORITHMS | 1993年 / 14卷 / 02期

关键词：

D O I：

10.1006/jagm.1993.1015

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We investigate the problem of linear broadcast, which is performed in a network in which messages follow linear routes. This is a characteristic of many high-speed networks, in which a special hardware is used for switching. Following, extending, and improving the recent work of Chou and Gopal (J. Algorithms10 (1989), 490-517), we study cases when the switching hardware has various limitations. We present algorithms that compute an optimal broadcast routing for any given number of linear routes. Our main result in an O(N) algorithm for the general problem of linear broadcast routing, for a tree network of size N for which an O(N2) algorithm was given by Chou and Gopal. © 1993 Academic Press, Inc.

引用

页码：288 / 315

页数：28

共 8 条

[1]

BITAN S, UNPUB OPTIMAL LINEAR

[2]

BITAN S, 1990, THESIS ISRAEL I TECH

[3]

BLUM M, 1973, J COMPUT SYST SCI, V7, P281

[4] LINEAR BROADCAST ROUTING [J].

CHOU, CT ;

GOPAL, IS .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1989, 10 (04) :490-517

[5]

CIDON I, 1988, 7TH P ANN ACM S PRIN, P75

[6]

CIDON I, 1988, J ANALOG DIGITAL JUN

[7]

COHEN R, 1987, 9TH P INT C COMP COM, P299

[8] DISTRIBUTED NETWORK PROTOCOLS [J].

SEGALL, A .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1983, 29 (01) :23-35

← 1 →