A GRASP for Coloring Sparse Graphs

被引：0
作者：
Manuel Laguna
Rafael Martí
机构：
[1] University of Colorado,Graduate School of Business
[2] Universidad de Valencia,Departamento de Estadística e Investigación Operativa
来源：
Computational Optimization and Applications | 2001年 / 19卷
关键词：
graph coloring; metaheuristics; GRASP;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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
页数：13
相关论文
共 35 条
  • [1] Bollobas B.(1985)Random graphs of small order Annals of Discrete Mathematics 28 249-255
  • [2] Thompson A.(1979)New methods to color vertices of a graph Comm. ACM 22 251-256
  • [3] Brelez D.(1987)Some experiments with simulated annealing for coloring graphs European Journal of Operational Research 32 260-266
  • [4] Chams M.(1983)Estimation of sparse Jacobian matrices and graph coloring problems SIAM J. Numer. Anal. 20 187-209
  • [5] Hertz A.(1995)An evolutionary tabu search algorithm and the NHL scheduling problem INFOR 33 161-178
  • [6] de Werra D.(1995)Embedding of a sequential procedure within an evolutionary algorithm for coloring problems in graphs Journal of Heuristics 1 105-128
  • [7] Coleman T.F.(1989)A probabilistic heuristic for a computationally difficult set covering problem Operations Research Letters 8 67-71
  • [8] More J.J.(1995)Greedy randomized adaptive search procedures Journal of Global Optimization 2 1-27
  • [9] Costa D.(1996)Genetic and hybrid algorithms for graph coloring Annals of Operations Research 63 437-464
  • [10] Costa D.(1988)Using tabu search techniques for graph coloring Computing 39 345-351
1234