TEST-CASE GENERATORS AND COMPUTATIONAL RESULTS FOR THE MAXIMUM CLIQUE PROBLEM

被引：38

作者：

HASSELBERG, J

PARDALOS, PM

VAIRAKTARAKIS, G

机构：

[1] KTH,DEPT COMP SCI,ROYAL INST TECHNOL,STOCKHOLM,SWEDEN

[2] UNIV FLORIDA,DEPT IND & SYST ENGN,GAINESVILLE,FL 32611

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 1993年 / 3卷 / 04期

关键词：

MAXIMUM CLIQUE PROBLEM; TESTING; GLOBAL OPTIMIZATION;

D O I：

10.1007/BF01096415

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In the last years many algorithms have been proposed for solving the maximum clique problem. Most of these algorithms have been tested on randomly generated graphs. In this paper we present different test problem generators that arise from a variety of practical applications, as well as graphs with known maximum cliques. In addition, we provide computational experience with two exact algorithms using the generated test problems.

引用

页码：463 / 482

页数：20

共 24 条

[1] MINIMUM WEIGHTED COLORING OF TRIANGULATED GRAPHS, WITH APPLICATION TO MAXIMUM WEIGHT VERTEX PACKING AND CLIQUE FINDING IN ARBITRARY GRAPHS [J].