Graph Connectivity

This work is mainly concerned with the strength of connections between vertices with respect to the number of vertex- or edge-disjoint paths. As we shall see, this is equivalent to the question of how many nodes or edges must be removed from a graph to destroy all paths between two (arbitrary or specified) vertices. We review algorithms which - check k-vertex (k-edge) connectivity, - compute the vertex (edge) connectivity, and - compute the maximal k-connected components of a given graph. After a few definitions we present some important theorems which summarize fundamental properties of connectivity and which provide a basis for understanding the algorithms in the subsequent sections. We give an introduction to minimum cuts and their properties, and discuss a structure for representing all minimum cuts, called cactus. Afterwards, we review connectivity algorithms that are based on network flow techniques. As examples for non-flow-based approaches, we summarize randomized connectivity algorithms and discuss a very simple algorithm for the (global) minimum capacity cut problem. The computation of biconnected, strongly connected, and triconnected components is considered in the penultimate section. The last section gives references for advanced topics and further reading.     «

This work is mainly concerned with the strength of connections between vertices with respect to the number of vertex- or edge-disjoint paths. As we shall see, this is equivalent to the question of how many nodes or edges must be removed from a graph to destroy all paths between two (arbitrary or specified) vertices. We review algorithms which - check k-vertex (k-edge) connectivity, - compute the vertex (edge) connectivity, and - compute the maximal k-connected components of a given graph. After...     »