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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageUnknown
Title of host publicationMathematics and Computers in Science and Engineering
EditorsC Bulucea, V Mladenov, E Pop, M Leba, N Mastorakis
Place of PublicationAG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE
PublisherWorld Scientific and Engineering Acad and Soc
Pages178-183
ISBN (Print)978-960-474-138-0
Publication statusPublished - 1 Jan 2009
Event14th WSEAS International Conference on Applied Mathematics -
Duration: 1 Jan 2009 → …

Conference

Conference14th WSEAS International Conference on Applied Mathematics
Period1/01/09 → …

Cite this