This article is cited in 3 papers

On solving the clique problem via the d. c. constraint problem

T. V. Gruzdeva

Institute of System Dynamics and Control Theory, Siberian Branch of the Russian Academy of Sciences

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.

UDC: 519.853.4

Received: 14.07.2008
Revised: 20.08.2008

Bibliographic databases:

• 
•