AN EFFICIENT DISTRIBUTED BRIDGE-FINDING ALGORITHM

Authors
CHAUDHURI P
Citation
P. Chaudhuri, AN EFFICIENT DISTRIBUTED BRIDGE-FINDING ALGORITHM, Information sciences, 81(1-2), 1994, pp. 73-85
Citations number
16
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information sciences → ACNP
ISSN journal
00200255
Volume
81
Issue
1-2
Year of publication
1994
Pages
73 - 85
Database
ISI
SICI code
0020-0255(1994)81:1-2<73:AEDBA>2.0.ZU;2-A
Abstract
An efficient algorithm is presented in this paper that finds the bridg es of a connected undirected graph on a distributed or network model o f computation. The algorithm uses O(n) messages and O(n) units of time , where n is the number of nodes of the graph.