On solving the maximum clique problem

被引：0
作者：
Antonina Kuznetsova
Alexander Strekalovsky
机构：
[1] Institute of System Dynamics and Control Theory SB of RAS,
来源：
Journal of Global Optimization | 2001年 / 21卷
关键词：
d.c. maximization; global optimality conditions; local search; linearized problem; global search algorithm;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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
页数：23
相关论文
共 15 条
  • [1] Bomze I.(1997)Evolution towards the maximum clique Journal of Global Optimization 10 143-164
  • [2] Gibbons L.E.(1995)A continuous based heuristic for the maximum clique problem Clique, Graph Coloring, and Satisfiability: Second DIMACS Implementation Challenge 26 103-124
  • [3] Hearn D.W.(1965)Maxima for graphs and a new proof of a theorem of Turán Cand. J. Math. 17 533-540
  • [4] Pardalos P.M.(1995)Relaxation labeling networks for the maximum clique problem Journal of Artificial Neural Networks 2 313-327
  • [5] Motzkin T.S.(1995)Feasible and infeasible maxima in a quadratic program for maximum clique Journal of Artificial Neural Networks 2 411-420
  • [6] Straus E.G.(1993)The search for a global maximum of a convex functional on an admissible set Comput. Math. and Math. Physics 33 315-328
  • [7] Pelillo M.(1998)Testing the ℜ-strategy for a Reverse Convex Problem Journal of Global Optimization 13 61-74
  • [8] Pelillo M.(1999)An approach to the solution of integer optimization problem Comput. Math. and Math. Physics 39 6-13
  • [9] Jagota A.(undefined)undefined undefined undefined undefined-undefined
  • [10] Strekalovsky A.S.(undefined)undefined undefined undefined undefined-undefined
12