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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---