A fast algorithm for the maximum clique problem

被引：418

作者：

Östergård, PRJ ^{[1
]}

机构：

[1] Helsinki Univ Technol, Dept Comp Sci & Engn, Helsinki 02015, Finland

来源：

DISCRETE APPLIED MATHEMATICS | 2002年 / 120卷 / 1-3期

基金：

芬兰科学院;

关键词：

The research was supported by the Academy of Finland;

D O I：

10.1016/S0166-218X(01)00290-6

中图分类号：

O29 [应用数学];

学科分类号：

070104 [应用数学];

摘要：

Given a graph, in the maximum clique problem, one desires to find the largest number of vertices, any two of which are adjacent. A branch-and-bound algorithm for the maximum clique problem-which is computationally equivalent to the maximum independent (stable) set problem-is presented with the vertex order taken from a coloring of the vertices and with a new pruning strategy. The algorithm performs successfully for many instances when applied to random graphs and DIMACS benchmark graphs. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：197 / 207

页数：11

共 11 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

APPLEGATE D, DFMAX C C PROGRAM

[3]

FINDING MAXIMUM CLIQUES IN ARBITRARY AND IN SPECIAL GRAPHS [J].

BABEL, L .

COMPUTING, 1991, 46 (04) :321-341

[4]

Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring [J].

Balas, E ;

Xue, J .

ALGORITHMICA, 1996, 15 (05) :397-412

[5]

Biggs N., 1990, GRAPH COLOURINGS, P87

[6]

AN EXACT ALGORITHM FOR THE MAXIMUM CLIQUE PROBLEM [J].

CARRAGHAN, R ;

PARDALOS, PM .

OPERATIONS RESEARCH LETTERS, 1990, 9 (06) :375-382

[7]

TEST-CASE GENERATORS AND COMPUTATIONAL RESULTS FOR THE MAXIMUM CLIQUE PROBLEM [J].

HASSELBERG, J ;

PARDALOS, PM ;

VAIRAKTARAKIS, G .

JOURNAL OF GLOBAL OPTIMIZATION, 1993, 3 (04) :463-482

[8]

Optimal binary one-error-correcting codes of length 10 have 72 codewords [J].

Östergård, PRJ ;

Baicheva, T ;

Kolev, E .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1999, 45 (04) :1229-1231

[9]

THE MAXIMUM CLIQUE PROBLEM [J].

PARDALOS, PM ;

XUE, J .

JOURNAL OF GLOBAL OPTIMIZATION, 1994, 4 (03) :301-328

[10]

Sewell E. C., 1998, INFORMS Journal on Computing, V10, P438, DOI 10.1287/ijoc.10.4.438

← 1 2 →