Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
✍ Scribed by Ramakrishna Thurimella
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 295 KB
- Volume
- 23
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
A certificate for the k connectivity k connectivity refers to both k-edge . connectivity and k-vertex connectivity unless explicitly stated otherwise of a graph
Ž . O kn . We present a distributed algorithm for computing a sparse certificate for k Ž . Ž . connectivity. Let f n and g n be the distributed time complexities of computing ' Ž Ž .
. distributed environment to run in O D q g n q n time. All algorithms improve on the previous best known time bounds. Our main focus in this paper is the time complexity. However, no more than a polynomial number of messages, each of size Ž . Olog n , are generated by the algorithm.