Volume 15, No 6, 2008, P. 20-33

UDC 519.853.4
T. V. Gruzdeva
On solving the clique problem via the d.c. constraint problem

Abstract:
The Maximum Weighted Clique Problem (MWCP) and the Maximum Clique Problem (MCP) are considered as continuous (nonconvex) problems with constraint given by the (d.c.) function which can be represented as the difference of two convex functions. For solving MWCP and MCP the Global Search Strategy is applied, that is the base of a heuristic algorithm. Each step of the algorithm is investigated. The computational effectiveness of this approach is illustrated in comparison with other approaches. 
Tabl. 4, bibl. 12.

Keywords: maximum clique, local search procedure, d.c. programming, global search algorithm.

Gruzdeva Tat’yana Vladimirovna ¹
1. Institute of System Dynamics and Control Theory, SB RAS,
134 Lermontov str., 664033 Irkutsk, Russia
e-mail: gruzdeva@icc.ru