Geodesic
On solving the clique problem via the d.\,c.~constraint problem
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 6, pp. 20-33.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : maximum clique
Keywords: local search procedure, d. c. programming, global search algorithm. 
@article{DA_2008_15_6_a2,
     author = {T. V. Gruzdeva},
     title = {On solving the clique problem via the d.\,c.~constraint problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {20--33},
     publisher = {mathdoc},
     volume = {15},
     number = {6},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_6_a2/}
}
TY  - JOUR
AU  - T. V. Gruzdeva
TI  - On solving the clique problem via the d.\,c.~constraint problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 20
EP  - 33
VL  - 15
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_6_a2/
LA  - ru
ID  - DA_2008_15_6_a2
ER  - 
%0 Journal Article
%A T. V. Gruzdeva
%T On solving the clique problem via the d.\,c.~constraint problem
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 20-33
%V 15
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2008_15_6_a2/
%G ru
%F DA_2008_15_6_a2
T. V. Gruzdeva. On solving the clique problem via the d.\,c.~constraint problem. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 6, pp. 20-33. http://geodesic.mathdoc.fr/item/DA_2008_15_6_a2/

[1] Vasilev F. P., Metody optimizatsii, Faktorial Press, M., 2002, 824 pp.

[2] Gruzdeva T. V., Strekalovskii A. S., “Lokalnyi poisk v zadachakh s nevypuklymi ogranicheniyami”, Zhurn. vychisl. matematiki i mat. fiziki, 47:3 (2007), 397–413 | MR | Zbl

[3] Ore O., Teoriya grafov, Mir, M., 1982, 336 pp. | MR

[4] Strekalovskii A. S., Elementy nevypukloi optimizatsii, Nauka, Novosibirsk, 2003, 352 pp.

[5] Strekalovskii A. S., “Ob ekstremalnykh zadachakh s d. c. ogranicheniyami”, Zhurn. vychisl. matematiki i mat. fiziki, 41:12 (2001), 1833–1843 | MR | Zbl

[6] Strekalovskii A. S., “Minimiziruyuschie posledovatelnosti v zadachakh s d. c. ogranicheniyami”, Zhurn. vychisl. matematiki i mat. fiziki, 45:3 (2005), 435–447 | MR | Zbl

[7] Berman P., Pelc A., “Distributed Fault Diagnosis for Multiprocessor Systems”, Proceedings of the 20th Annual International Symposium on Fault-Tolerant Computing, Newcastle upon Tyne, UK, 1990, 340–346

[8] Bomze I. M., Budinich M., Pardalos P. M., Pelillo M., “The maximum clique problem”, Handbook of Combinatorial Optimization, Vol. A, Kluwer, Dordrecht, 1999, 1–74 | MR

[9] Kovalyov M. Y., Ng C. T., Edwin Cheng T. C., “Fixed interval scheduling: Models, applications, computational complexity and algorithms”, European J. Operational Research, 178 (2007), 331–342 | DOI | MR | Zbl

[10] Kuznetsova A., Strekalovsky A. S., “On solving the maximum clique problem”, J. Global Optim., 21:3 (2001), 265–288 | DOI | MR | Zbl

[11] Mannino C., Stefanutti E., “An augmentation algorithm for the maximum weighted stable set problem”, Comput. Optimization and Applications, 14:3 (1999), 467–371 | MR

[12] Stanislav Busygin, QualexMS: Quick Almost Exact maximum weight clique solver based on a generalized Motzkin-Straus formulation, ver. 1.2, , 2000–2007 http://: clp.pisem.net/LINKS/TSP/NP-CompletenessPage_20010710.htm