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 条

[1]

Bollobas B, 1985, ANN DISCRETE MATH, V28, P249

[2] NEW METHODS TO COLOR THE VERTICES OF A GRAPH [J].

BRELAZ, D .

COMMUNICATIONS OF THE ACM, 1979, 22 (04) :251-256

[3] SOME EXPERIMENTS WITH SIMULATED ANNEALING FOR COLORING GRAPHS [J].

CHAMS, M ;

HERTZ, A ;

DEWERRA, D .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1987, 32 (02) :260-266

[4] ESTIMATION OF SPARSE JACOBIAN MATRICES AND GRAPH-COLORING PROBLEMS [J].

COLEMAN, TF ;

MORE, JJ .

SIAM JOURNAL ON NUMERICAL ANALYSIS, 1983, 20 (01) :187-209

[5]

Costa D., 1995, Journal of Heuristics, V1, P105, DOI 10.1007/BF02430368

[6]

COSTA D, 1995, INFOR, V33, P161

[7]

Dahl E. D., 1987, IEEE First International Conference on Neural Networks, P113

[8]

EIBEN AE, 1997, GRAPH COLORING ADAPT

[9] GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES [J].

FEO, TA ;

RESENDE, MGC .

JOURNAL OF GLOBAL OPTIMIZATION, 1995, 6 (02) :109-133

[10] A PROBABILISTIC HEURISTIC FOR A COMPUTATIONALLY DIFFICULT SET COVERING PROBLEM [J].

FEO, TA ;

RESENDE, MGC .

OPERATIONS RESEARCH LETTERS, 1989, 8 (02) :67-71

← 1 2 3 →