1.5.3 Vertex Cover

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A graph G=(V,E) .

Problem: What is the smallest subset S \subset V such that each e \in E contains at least one vertex of S ?

Implementations

  • Neural-Networks for Cliques and Coloring (C) (rating 6)
  • DIMACS Implementation Challenges (FORTRAN) (rating 5)
  • Combinatorica (Mathematica) (rating 4)

    Related Problems

  • Clique
  • Independent Set
  • Set Cover

    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 .