An optimal distributed algorithm for finding a set of fundamental cycles in a graph

被引：0
作者：
Chaudhuri, P [1 ]
机构：
[1] Univ W Indies, Dept Comp Sci Math & Phys, Bridgetown, Barbados
来源：
COMPUTER SYSTEMS SCIENCE AND ENGINEERING | 2002年 / 17卷 / 01期
关键词：
distributed algorithm; undirected graph; fundamental cycles; message complexity;
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
A distributed algorithm for finding a set of fundamental cycles is presented in this paper. The output of the algorithm is available in a distributed manner, i.e. when the algorithm terminates each node knows the list of all the fundamental cycles passing through itself. The algorithm requires O(n) messages and O(n) units of time, where n is the number of nodes of the graph. It is shown that the algorithm is optimal in communication complexity to within a constant factor.
引用
收藏
页码：41 / 47
页数：7
相关论文
共 20 条
[1]  
Aho A.V., 1974, The Design and Analysis of Computer Algorithms
[2]   A NEW DISTRIBUTED DEPTH-1ST-SEARCH ALGORITHM [J].
AWERBUCH, B .
INFORMATION PROCESSING LETTERS, 1985, 20 (03) :147-150
[3]   DISTRIBUTED COMPUTATION ON GRAPHS - SHORTEST-PATH ALGORITHMS [J].
CHANDY, KM ;
MISRA, J .
COMMUNICATIONS OF THE ACM, 1982, 25 (11) :833-837
[4]   ECHO ALGORITHMS - DEPTH PARALLEL OPERATIONS ON GENERAL GRAPHS [J].
CHANG, EJH .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1982, 8 (04) :391-401
[5]   AN EFFICIENT DISTRIBUTED BRIDGE-FINDING ALGORITHM [J].
CHAUDHURI, P .
INFORMATION SCIENCES, 1994, 81 (1-2) :73-85
[6]   DISTRIBUTED-PROCESSING OF GRAPHS - FUNDAMENTAL CYCLES ALGORITHM [J].
CHAUDHURI, P .
INFORMATION SCIENCES, 1992, 60 (1-2) :41-50
[7]  
CHAUDHURI P, 1992, PARALLEL ALGORITHMS
[8]  
CHEUNG TY, 1983, IEEE T SOFTWARE ENG, V9, P504, DOI 10.1109/TSE.1983.234958
[9]   AN EFFICIENT DISTRIBUTED KNOT DETECTION ALGORITHM [J].
CIDON, I .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1989, 15 (05) :644-649
[10]   YET ANOTHER DISTRIBUTED DEPTH-1ST-SEARCH ALGORITHM [J].
CIDON, I .
INFORMATION PROCESSING LETTERS, 1988, 26 (06) :301-305
12