An optimal distributed ear decomposition algorithm with applications to biconnectivity and outerplanarity testing

摘要

We present an asynchronous distributed algorithm to determine an ear decomposition of an arbitrary, connected, bi-directional network containing n-nodes and m-links using O(m) messages and O(n) time. Using the ear decomposition we obtain the following results: 1. The distributed ear decomposition algorithm can be used to test biconnectivity, determine biconnected components, find outpoints and bridges using O(m) messages in O(n) time. 2. The distributed ear decomposition algorithm can be used to test if a network is outerplanar using O(n) messages in O(n) time and if the network is outerplanar the embedding is also given using the same message and time complexity.