(thing) by flyingroc Fri Nov 10 2000 at 19:59:09
An independent set, in graph theory, is a set of vertices that are not connected to each other by an edge. Any set with exactly one vertex is an independent set.

The independent set problem is: given a graph and an integer k, is there an independent set with the number of vertices >= k?

The independent set problem has been proven to be np-complete by a reduction from clique.

del.icio.us Facebook Digg StumbleUpon Reddit (I like it!)
Y'know, if you log in, you can write something here, or contact authors directly on the site. Create a New User if you don't already have an account.