Untitled
unknown
plain_text
a year ago
726 B
3
Indexable
Never
1: V0 V fthe current set of vertices consists of applicants for inclusion in the independent setg 2: S fg 3: Est 0 4: while V0 6= fg do 5: for all v 2 V0 do 6: calculate k[v] 7: calculate m[v] 8: end for 9: v0 MinMaxParam(v) 10: S S [ fv0g 11: Est Est + m[v0] 12: V0 V0 fv0g N (v0; V0)fremove from the set of applicants the selected vertex together with neighborhoodg 13: end while This algorithm was implemented and used to nd the maximum indepen- dent set in complementary graphs DIMACS. It is clear that in the initial graph the solution obtained will correspond to the clique. Then it became possible to compare results with other eective algorithms.