next up previous contents index CD CD Algorithms
Next: Circuit Board Placement Up: Simulated Annealing Previous: Maximum Cut

Independent Set

An independent set of a graph G is a subset of vertices S such that there is no edge with both endpoints in S. The maximum independent set of a graph is the largest such empty induced subgraph. The need to find large independent sets arises in dispersion problems associated with facility location and coding theory, as discussed in catalog Section gif.  

The natural state space for a simulated annealing solution would be all tex2html_wrap_inline25878 subsets of the vertices, represented as a bit vector. As with maximum cut above, a simple transition mechanism would be to add or delete one vertex from S.

One natural cost function for subset S might be 0 if S contains an edge, and |S| if it is indeed an independent set. This function ensures that we work towards an independent set at all times. However, this condition is strict enough that we are liable to move only in a narrow portion of the possible search space. More flexibility in the search space and quicker cost function computations can result from allowing non-empty graphs at the early stages of cooling. Better in practice would be a cost function like tex2html_wrap_inline25882 , where tex2html_wrap_inline25884 is a constant, T is the temperature, and tex2html_wrap_inline25886 is the number of edges in the subgraph induced by S. The dependence of C(S) on T ensures that the search will drive the edges out faster as the system cools.

Mon Jun 2 23:33:50 EDT 1997