Untitled

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.