Sub-linear distributed algorithms for sparse certificates and biconnected components
Ramakrishna Thurimella · 1995
A certificatefor the k connectivityIV[ and m = IE1.A certificate is called sparse if it has size O(kn).We present a distributed algorithm for computing sparse certificate fork connectivity whose time complexity is O(k(D + n0614 )) where D is the diameter of the network.A new algorithm for identifying biconnected components is also presented.This algorithm is significantly simpler than many existing algorithms and can be implemented in distributed environment to run iu O(D + no "614) time.Both 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 O(log n), are generated by the algorithm.