On 11/29/06, Ken1 <[EMAIL PROTECTED]> wrote:
>
> ok, can anybody indicate an algorithm that would verify if there exists
> a set of k independent vertices in a graph ?
>
If you are talking about the decision problem -
"Does there exist an independent set of size k in the graph?"
As already mentioned, this problem is NP-Complete.
For proving the correctness of a given solution:
Given G = {V,E}, and a set of vertices S (possible soution), we have
to find out whether the given set of vertices is an independent set.
for each vertex u in S
for each vertex v in {S \ u}
if edge uv belongs to E
return FALSE;
return TRUE;
Hope this helps.
nilesh
--
And ye shall know the truth (source) and the truth shall set you free.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
