This chapter presents an exposition of how connectivity algorithms have advanced over the years. Most of these algorithms work by making a number of calls to a max-flow subroutine. As these calls determine the bulk of the computation, attempts have been made to minimize the number of such calls.
A variety of algorithms for the computation of the vertex-connectivity κ(G) and the edge-connectivity λ(G) of a graph G have been developed over the years. Most of these algorithms work by solving a number of maximum-flow problems ...