The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.4.8 Edge and Vertex Connectivity

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A graph G. Optionally, a pair of vertices s and t.

Problem: What is the smallest subset of vertices (edges) whose deletion will disconnect G? Alternately, what is the smallest subset of vertices (edges) which will separate s from t?

Excerpt from The Algorithm Design Manual: Graph connectivity often arises in problems related to network reliability. In the context of telephone networks, the vertex connectivity is the smallest number of switching stations that a terrorist must bomb in order to separate the network, \ie prevent two unbombed stations from talking to each other. The edge connectivity is the smallest number of wires that need to be cut to accomplish the same thing. One well-placed bomb or snipping the right pair of cables suffices to disconnect the network above.

The edge (vertex) connectivity of a graph G is the smallest number of edge (vertex) deletions sufficient to disconnect G. There is a close relationship between the two quantities. The vertex connectivity is always no smaller than the edge connectivity, since deleting one vertex incident on each edge in a cut set succeeds in disconnecting the graph. Of course, smaller vertex subsets may be possible. The minimum vertex degree is an upper bound on both the edge and vertex connectivity, since deleting all its neighbors (or the edges to all its neighbors) disconnects the graph into one big and one single-vertex component.


Implementations

  • Goldberg's Network Optimization Codes (C) (rating 10)
  • Boost: C++ Libraries (C++) (rating 9)
  • GOBLIN: A Graph Object Library for Network (C++) (rating 8)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 8)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 4)
  • Combinatorica (Mathematica) (rating 4)

  • Recommended Books

    Randomized Algorithms by R. Motwani and P. Raghavan Network Flows : Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin Graph Algorithms by S. Even
    Flows in Networks by L. Ford and D. R. Fulkerson

    Related Problems


      
    Connected Components
      
    Graph Partition
      
    Network Flow



    This page last modified on 2008-07-10 .
    www.algorist.com