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.

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.