zbMATH — the first resource for mathematics

An efficient distributed algorithm for finding articulation points, bridges, and biconnected components in asynchronous networks. (English) Zbl 0734.68013
Foundations of software technology and theoretical computer science, Proc. 9th Conf., Bangalore/India 1989, Lect. Notes Comput. Sci. 405, 99-108 (1989).
Summary: [For the entire collection see Zbl 0728.00019.]
Let a network be represented as \(G=(V,E)\), with \(| V| =n\) and \(| E| =m\). The algorithm uses the distributed depth first search (DDFS) algorithm proposed independently by I. Cidon [Yet another distributed depth-first-search algorithm, Inf. Process. Lett. 26(6), 301- 305 (1988)] and K. Lakshmanan, N. Meenakshi and K. Thulasiraman [A time-optimal message-efficient distributed algorithm for depth first search, Inf. Process. Lett. 25(2), 103-109 (1987)], both improved an earlier DDFS algorithm of B. Awerbuch [Inf. Process. Lett. 20, 147-150 (1985; Zbl 0573.68013)] using the same idea. It can detect all the articulation points and bridges, and identify all the members of each biconnected component through one run of a DDFS. The algorithm is efficient in the sense that its time is only 2n-2 (which is optimal), number of messages is bounded by 4m-n, each message size is bounded by 2log n\(+2\) bits and there is no complicated local computations. It can operate correctly in asynchronous networks, specially message passing does not need to be in FIFO order.
68M10 Network design and communication in computer systems
68W15 Distributed algorithms
68Q25 Analysis of algorithms and problem complexity