A distributed algorithm for constructing a minimum diameter spanning tree

被引：32

作者：

Bui, M

Butelle, F

Lavault, C

机构：

[1] Univ Paris 13, CNRS, UMR A7030, Lab Rech LIPN, F-93430 Villetaneuse, France

[2] Univ Paris 08, Lab Rech LDCI, F-93526 St Denis 02, France

来源：

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 2004年 / 64卷 / 05期

关键词：

spanning trees; minimum diameter spanning trees; shortest paths; shortest paths trees; all-pairs shortest paths; absolute centres;

D O I：

10.1016/j.jpdc.2004.03.009

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a new algorithm, which solves the problem of distributively finding a minimum diameter spanning tree of any (non-negatively) real-weighted graph G = (V, E, (omega)). As an intermediate step, we use a new, fast, linear-time all-pairs shortest paths distributed algorithm to find an absolute centre of G. The resulting distributed algorithm is asynchronous, it works for named asynchronous arbitrary networks and achieves O(\V\) time complexity and O(\V\ \E\) message complexity. (C) 2004 Elsevier Inc. All rights reserved.

引用

页码：571 / 577

页数：7

共 18 条

[1]

Awerbuch B., 1990, Proceedings. 31st Annual Symposium on Foundations of Computer Science (Cat. No.90CH2925-6), P492, DOI 10.1109/FSCS.1990.89570

[2] COMPLEXITY OF NETWORK SYNCHRONIZATION [J].

AWERBUCH, B .

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

[3]

Awerbuch B., 1987, P 19 ANN ACM S THEOR, P230, DOI DOI 10.1145/28395.28421.URL

[4]

Bertsekas D. P., 1992, DATA NETWORKS

[5]

BUI M, 1993, P INT WORKSH PRINC P, P37

[6] COMPLEXITY OF SPANNING TREE PROBLEMS .1. [J].

CAMERINI, PM ;

GALBIATI, G ;

MAFFIOLI, F .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1980, 5 (05) :346-352

[7] A MESSAGE-OPTIMAL ALGORITHM FOR DISTRIBUTED TERMINATION DETECTION [J].

CHANDRASEKARAN, S ;

VENKATESAN, S .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1990, 8 (03) :245-252

[8] MAINTENANCE OF A MINIMUM SPANNING FOREST IN A DYNAMIC PLANE GRAPH [J].

EPPSTEIN, D ;

ITALIANO, GF ;

TAMASSIA, R ;

TARJAN, RE ;

WESTBROOK, J ;

YUNG, M .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1992, 13 (01) :33-54

[9]

FRAIGNIAUD P, 1995, 9505 LIP ENSL

[10] 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

← 1 2 →