Computing Bridges, Articulations, and 2-Connected Components in Wireless Sensor Networks

Date Added: Aug 2009
Format: PDF

This paper presents a simple distributed algorithm to determine the bridges, articulation points, and 2-connected components in asynchronous networks with an at least once message delivery semantics in time O(n) using at most 4m messages of length O(lg n). The algorithm does not assume a FIFO rule for message delivery. Previously known algorithms either use longer messages or need more time. The algorithm meets the requirements of wireless senor networks and can be applied in several areas relevant to this field such as topology control, clustering, localization and virtual backbone calculations.