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 G - F in polynomial time with respect to |F| and the maximum degree of G. We present two approaches.

The first algorithm is designed for graphs with good vertex expansion, while the other solution applies to the class of graphs with cycle basis consisting of cycles of bounded length. We also present an extension of the latter method to test the biconnectivity of G - F.

Keywords

• biconnectivity
• connectivity
• cycle basis
• faulty vertex
• interconnection network
• vertex expansion