Complementary approaches for the computation of the independent number of a graph

Citation:
Brás, C. P., and J. J. Júdice Complementary approaches for the computation of the independent number of a graph. Proceedings of the 14th WSEAS International Conference on Applied Mathematics (MATH’09). Tenerife, Spain, 2009.

Abstract:

The problem of finding the independent number of an undirected graph is formulated as two equivalent Mathematical Programs with Linear Complementarity Constraints (MPLCC). A multistarting Lemke’s method
is introduced for dealing with the first formulation and is able to find a good approximate of the independent
number in a finite number of iterations. A sequential complementary algorithm is also discussed for the second formulation and can find the independent number at least in theory. Some computational experience is included to highlight the efficacy of the complementary approaches for computing the independent number of graphs from the Dimacs collection.