The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.5.2 Independent Set

Problem Input | Problem Output

INPUT                    OUTPUT


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

Problem: What is the largest subset of vertices of V such that no pair of vertices defines an edge of E?

Excerpt from The Algorithm Design Manual: The need to find large independent sets typically arises in dispersion problems, where we seek a set of mutually separated points. For example, suppose you are trying to identify locations for a new franchise service such that no two locations are close enough to compete with each other. Construct a graph where the vertices are possible locations, and add edges between any two locations deemed close enough to interfere. The maximum independent set gives you the maximum number of franchises you can sell without cannibalizing sales.

Independent sets avoid conflicts between elements and hence arise often in coding theory and scheduling problems. Define a graph whose vertices represent the set of possible code words, and add edges between any two code words sufficiently similar to be confused due to noise. The maximum independent set of this graph defines the highest capacity code for the given communication channel.


Implementations

  • GOBLIN: A Graph Object Library for Network (C++) (rating 9)
  • GRASP- Greedy randomized adaptive search program (FORTRAN) (rating 8)
  • RAPID - Robust and Accurate Polygon Interface detection (C,FORTRAN) (rating 5)
  • GMT - Graph Matching Toolkit (Binary) (rating 4)
  • Neural-Networks for Cliques and Coloring (C,Mathematica) (rating 4)

  • Recommended Books

    Cliques, Coloring, and Satisfiability: Second Dimacs Implementation Challenge by David S. Johnson and Michael A. Trick, Editors Computers and Intractability: A Guide to the Theory of NP-Completeness by M. R. Garey and D. S. Johnson Combinatorial Optimization: Networks and Matroids by E. Lawler

    Related Problems


      
    Clique
      
    Set Packing
      
    Vertex Coloring
      
    Vertex Cover



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