A new derivation of Frisch's algorithm for calculating vertex-pair connectivity

In this paper we give a new and conceptually simple version of Frisch's algorithm for calculating the vertex connectivity of a graph. We show how this algorithm is obtained immediately from the Ford and Fulkerson labelling algorithm by using a 2-ply scanning step. Data structures are introduced which lead to efficiencies in execution, and the final algorithm is presented in a go-to-less notation.This work was supported in part by U.S. Army Research Office, Durham under contract DA HC04 69 C 0012, and NSF Grant GJ-965.