A GRASP for coloring sparse graphs

被引：32

作者：

Laguna, M ^{[1
]}

Martí, R

机构：

[1] Univ Colorado, Grad Sch Business, Boulder, CO 80309 USA

[2] Univ Valencia, Dept Estadist & Invest Operat, E-46003 Valencia, Spain

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 2001年 / 19卷 / 02期

关键词：

graph coloring; metaheuristics; GRASP;

D O I：

10.1023/A:1011237503342

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We first present a literature review of heuristics and metaheuristics developed for the problem of coloring graphs. We then present a Greedy Randomized Adaptive Search Procedure (GRASP) for coloring sparse graphs. The procedure is tested on graphs of known chromatic number, as well as random graphs with edge probability 0.1 having from 50 to 500 vertices. Empirical results indicate that the proposed GRASP implementation compares favorably to classical heuristics and implementations of simulated annealing and tabu search. GRASP is also found to be competitive with a genetic algorithm that is considered one of the best currently available for graph coloring.

引用

页码：165 / 178

页数：14

共 26 条

[11] Genetic and hybrid algorithms for graph coloring [J].

Fleurent, C ;

Ferland, JA .

ANNALS OF OPERATIONS RESEARCH, 1996, 63 :437-461

[12]

Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness

[13] USING TABU SEARCH TECHNIQUES FOR GRAPH-COLORING [J].

HERTZ, A ;

DEWERRA, D .

COMPUTING, 1987, 39 (04) :345-351

[14]

Holland J., 1992, ADAPTATION NATURAL A

[15]

HOPFIELD JJ, 1985, BIOL CYBERN, V52, P141

[16] An adaptive, multiple restarts neural network algorithm for graph coloring [J].

Jagota, A .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 93 (02) :257-270

[17] OPTIMIZATION BY SIMULATED ANNEALING - AN EXPERIMENTAL EVALUATION .2. GRAPH-COLORING AND NUMBER PARTITIONING [J].

JOHNSON, DS ;

ARAGON, CR ;

MCGEOCH, LA ;

SCHEVON, C .

OPERATIONS RESEARCH, 1991, 39 (03) :378-406

[18] OPTIMIZATION BY SIMULATED ANNEALING [J].

KIRKPATRICK, S ;

GELATT, CD ;

VECCHI, MP .

SCIENCE, 1983, 220 (4598) :671-680

[19] GRAPH-COLORING ALGORITHM FOR LARGE SCHEDULING PROBLEMS [J].

LEIGHTON, FT .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS, 1979, 84 (06) :489-506

[20]

LEWANDOWSKI G, 1993, 1213 U WISC COMP SCI

← 1 2 3 →