Testing connectivity of faulty networks in sublinear time.

Abstract: Given a set F of vertices of a connected graph G, we study the problem of testing the connectivity of in polynomial time with respect to and the maximum degree Δ of G. We present two approaches. The first algorithm for this problem runs in time for every graph G with vertex expansion at least . The other solution, designed for the class of graphs with cycle basis consisting of cycles of length at most l, leads to running time. We also present an extension of this method to test the biconnectivity of in time. [Copyright &y& Elsevier]