A DISTRIBUTED SHORTEST-PATH ALGORITHM FOR A PLANAR NETWORK

被引：7

作者：

FREDERICKSON, GN

机构：

[1] Department of Computer Sciences, Purdue University, West Lafayette

来源：

INFORMATION AND COMPUTATION | 1990年 / 86卷 / 02期

基金：

俄罗斯科学基金会;

关键词：

D O I：

10.1016/0890-5401(90)90051-I

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An algorithm is presented for finding a single source shortest path tree in a planar undirected distributed network with nonnegative edge costs. The number of messages used by the algorithm is O(n 5 3) on an n-node network. Distributed algorithms are also presented for finding a breath-first spanning tree in general network, for finding a shortest path tree in a general network, for finding a separator of a planar network, and for finding a division of a planar network. © 1990.

引用

页码：140 / 159

页数：20

共 14 条

[1]

ABRAM JM, 1978, 16TH P ANN ALL C COM, P271

[2]

Awerbuch B., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P250, DOI 10.1109/SFCS.1985.20

[3] A NEW DISTRIBUTED ALGORITHM TO FIND BREADTH 1ST SEARCH-TREES [J].

AWERBUCH, B ;

GALLAGER, RG .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1987, 33 (03) :315-322

[4]

AWERBUCH B, 1989, 21ST P ACM S THEOR C, P490

[5]

Dijkstra EW., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390

[6]

FREDERICKSON GN, 1987, SIAM J COMPUT, V16, P1004, DOI 10.1137/0216064

[7]

FREDERICKSON GN, 1985, 2ND P S THEOR ASP CO, P143

[8]

FRIEDMAN DU, 1979, LIDSTH886 MIT

[9] A DISTRIBUTED ALGORITHM FOR MINIMUM-WEIGHT SPANNING-TREES [J].

GALLAGER, RG ;

HUMBLET, PA ;

SPIRA, PM .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1983, 5 (01) :66-77

[10]

GALLAGER RG, 1982, MIT LIDSP1175 TECHN

← 1 2 →