THE STEINER PROBLEM IN DISTRIBUTED COMPUTING SYSTEMS

被引：26

作者：

CHEN, GH ^{[1
]}

HOULE, ME ^{[1
]}

KUO, MT ^{[1
]}

机构：

[1] UNIV NEWCASTLE,DEPT COMP SCI,NEWCASTLE,NSW 2308,AUSTRALIA

来源：

INFORMATION SCIENCES | 1993年 / 74卷 / 1-2期

关键词：

D O I：

10.1016/0020-0255(93)90128-9

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A distributed algorithm is presented for constructing a nearly optimal Steiner tree in an asynchronous network represented by a weighted communication graph G = (V, E, c). The worst-case cost ratio of the obtained solution to any given minimum-cost Steiner tree T(min) is 2(1 - 1/l), where l is the number of leaves of T(min). The message complexity of the algorithm is O(Absolute value of E + Absolute value of V*(\V\S\+log Absolute value of V)) and the time complexity is O Absolute value of V*\v\S\), where S is the subset of nodes of G to be connected.

引用

页码：73 / 96

页数：24

共 23 条

[1]

[Anonymous], 1980, MATH JAPONICA

[2]

[Anonymous], 1983, DATA STRUCTURES NETW, DOI DOI 10.1137/1.9781611970265

[3] COMPLEXITY OF NETWORK SYNCHRONIZATION [J].

AWERBUCH, B .

JOURNAL OF THE ACM, 1985, 32 (04) :804-823

[4]

AWERBUCH B, 1986, 27TH P ANN S F COMP

[5]

AWERBUCH B, 1987, 19TH P ANN ACM S THE, P230

[6]

Chin F., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P257, DOI 10.1109/SFCS.1985.7

[7]

CIMET I, 1987, 1987 P INT C PAR PRO, P196

[8] A DISTRIBUTED ALGORITHM FOR CONSTRUCTING MINIMAL SPANNING-TREES [J].

DALAL, YK .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1987, 13 (03) :398-405

[9] REVERSE PATH FORWARDING OF BROADCAST PACKETS [J].

DALAL, YK ;

METCALFE, RM .

COMMUNICATIONS OF THE ACM, 1978, 21 (12) :1040-1048

[10]

DEO N, 1974, GRAPH THEORY APPLICA

← 1 2 3 →