Testing connectivity of faulty networks in sublinear time ?
Given a set F of vertices of a connected graph G , we study the problem of testing the connectivity of G?F G ? F in polynomial time with respect to |F| | F | and the maximum degree ? of G . We present two approaches. The first algorithm for this problem runs in O(|F|?2??1log(|F|???1)) O ( | F | ? 2 ? ? 1 log ( | F | ? ? ? 1 ) ) time for every graph G  with vertex expansion at least ?>0 ? > 0 . The other solution, designed for the class of graphs with cycle basis consisting of cycles of length at most l , leads to O(|F|??l/2?log(|F|??l/2?)) O ( | F | ? ? l / 2 ? log ( | F | ? ? l / 2 ? ) ) running time. We also present an extension of this method to test the biconnectivity of G?F G ? F in O(|F|?llog(|F|?l)) O ( | F | ? l log ( | F | ? l ) ) time.
connectivity vertex expansion cycle basis biconnectivity faulty vertex interconnection network