On solving the maximum clique problem

被引：7
作者：
Kuznetsova, A [1 ]
Strekalovsky, A [1 ]
机构：
[1] RAS, Inst Syst Dynam & Control Theory SB, Irkutsk 664033 33, Russia
来源：
JOURNAL OF GLOBAL OPTIMIZATION | 2001年 / 21卷 / 03期
基金：
俄罗斯基础研究基金会;
关键词：
d.c; maximization; global optimality conditions; local search; linearized problem; global search algorithm;
D O I：
10.1023/A:1012395712371
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
The Maximum Clique Problem (MCP) is regarded here as the maximization of an indefinite quadratic form over the canonical simplex. For solving MCP an algorithm based upon Global Optimality Conditions (GOC) is applied. Furthermore, each step of the algorithm is analytically investigated and tested. The computational results for the proposed algorithm are compared with other Global Search approaches.
引用
收藏
页码：265 / 288
页数：24
相关论文
共 15 条
  • [1] [Anonymous], 1999, HDB COMBINATORIAL OP
  • [2] Bazaraa MokhtarS., 1979, Nonlinear Programming: Theory and Algorithms
  • [3] Evolution towards the maximum clique
    Bomze, IM
    [J]. JOURNAL OF GLOBAL OPTIMIZATION, 1997, 10 (02) : 143 - 164
  • [4] BOMZE IM, 1997, DEV GLOBAL OPTIMIZAT, V18, P95
  • [5] Carey M., 1979, COMPUTER INTRACTABIL
  • [6] GIBBONS LE, 1995, 2 DIMACS IMPLEMENTAT, V26, P103
  • [7] Horst R., 1995, INTRO GLOBAL OPTIMIZ, V3
  • [8] KUZNETSOVA AA, 1999, COMP MATH MATH PHYS+, V39, P6
  • [9] MAXIMA FOR GRAPHS AND A NEW PROOF OF A THEOREM OF TURAN
    MOTZKIN, TS
    STRAUS, EG
    [J]. CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (04): : 533 - &
  • [10] Pelillo M., 1995, Journal of Artificial Neural Networks, V2, P313
12