A GLOBAL OPTIMIZATION APPROACH FOR SOLVING THE MAXIMUM CLIQUE PROBLEM

被引：51
作者：
PARDALOS, PM [1 ]
PHILLIPS, AT [1 ]
机构：
[1] USN ACAD,DEPT COMP SCI,ANNAPOLIS,MD 21402
来源：
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 1990年 / 33卷 / 3-4期
关键词：
Global optimization; maximum clique problem;
D O I：
10.1080/00207169008803851
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The problem of finding a maximum clique of an undirected graph is formulated and solved as a linearly constrained indefinite quadratic global optimization problem. Theoretical upper and lower bounds on the size k of the maximum clique are derived from the global optimization formulation, and a relationship between the set of distinct global maxima of the optimization problem and the set of distinct maximum cliques of the graph is discussed. In addition, some preliminary computational results are also presented. © 1990, Taylor & Francis Group, LLC. All rights reserved.
引用
收藏
页码：209 / 216
页数：8
相关论文
共 12 条
[1]   UPPER BOUNDS ON ORDER OF A CLIQUE OF A GRAPH [J].
AMIN, AT .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1972, 22 (04) :569-&
[2]   FINDING A MAXIMUM CLIQUE IN AN ARBITRARY GRAPH [J].
BALAS, E ;
YU, CS .
SIAM JOURNAL ON COMPUTING, 1986, 15 (04) :1054-1068
[3]   FINDING ALL CLIQUES OF AN UNDIRECTED GRAPH [H] [J].
BRON, C ;
KERBOSCH, J .
COMMUNICATIONS OF THE ACM, 1973, 16 (09) :575-577
[4]  
Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[5]   CLIQUE DETECTION FOR NONDIRECTED GRAPHS - 2 NEW ALGORITHMS [J].
GERHARDS, L ;
LINDENBERG, W .
COMPUTING, 1979, 21 (04) :295-322
[6]  
HAGER WW, 1987, ACTIVE CONSTRAINTS O
[7]   DETERMINING THE NUMBER OF INTERNAL STABILITY OF A GRAPH [J].
LOUKAKIS, E ;
TSOUROS, C .
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1982, 11 (3-4) :207-220
[8]   MAXIMA FOR GRAPHS AND A NEW PROOF OF A THEOREM OF TURAN [J].
MOTZKIN, TS ;
STRAUS, EG .
CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (04) :533-&
[9]  
PARDALOS PM, 1987, LECTURE NOTES COMPUT, V268
[10]  
PARDALOS PM, 1988, BRANCH BOUND ALGORIT
12