1.4.8 Edge and Vertex Connectivity

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A graph G . Optionally, a pair of vertices 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 from t ?

Implementations

  • Combinatorica (Mathematica) (rating 4)
  • The Stanford GraphBase (C) (rating 4)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 4)

    Related Problems

  • Connected Components
  • Graph Partition
  • Network Flow

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .