A DEPTH-FIRST SEARCH CHARACTERIZATION OF K-CONNECTIVITY AND ITS APPLICATION TO CONNECTIVITY TESTING

Abstract

The vertex connectivity of an undirected graph is explored with regard to a depth-first search analysis. This analysis leads to a separating set characterization theorem of a very general nature. The strength of this characterization is illustrated by an application to triconnectivity testing. The resulting preorder algorithm will list all non-degenerate separating pairs in time O(E(alpha)(E,V)+(mu)(,2)) and space O(E) where (mu)(,2) is the number of separating pairs. This characterization also suggests an O(ElogE) algorithm for 4-connectivity testing. Some preliminary results for this algorithm are presented.