From TheBestLinks.com
In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V' (a subset of V) such that for every two vertices in V', there is no edge connecting the two. Or, more simply put, a set of vertices such that none of them are connected by an edge. The size of a independent set is the number of vertices it contains.
The maximum independent-set problem refers to the problem of finding the largest independent-set in any graph G. This problem is NP-complete, and as such, it is very unlikely that an efficient algorithm for finding the largest independent-set of a graph exists.
The opposite of a independent set is a clique. If we already know that the clique problem is NP-complete, then it is easy to prove, as the size of a independent set is the same as the size of the largest clique in the inverse graph.
Maximum independent set problem is not be confused with maximal independent set problem. A maximal independent set is an independent set which is not contained in any larger independent set. The problem of finding a maximal independent set is solvable in polynomial time by a very simple algorithm. This algorithm starts with an empty set V. Then it searches for a vertex v that is not connected to any vertex in V and if such v is found, adds v to V. The algorithm stops when it cannot find v not connected to any vertex in V. This results in an independent set that is not contained in any larger independent set.
Related links
Top visited
0 of
0 links
[no links posted yet]
>> place link >>
Discussion
Last posted
0 of
0 messages
[no messages posted yet]
>> post message >>
Watch
You can
add this article to your own "watchlist" and receive e-mail notification about all changes in this page.
