On the recursive largest first algorithm for graph colouring

被引：11
作者：
Palubeckis, G. [1 ]
机构：
[1] Kaunas Univ Technol, Dept Pract Informat, LT-3031 Kaunas, Lithuania
来源：
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 2008年 / 85卷 / 02期
关键词：
combinatorial optimization; graph colouring; heuristics; independent set;
D O I：
10.1080/00207160701419114
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We present a reduction from the problem of colouring the vertices of the graph to the maximum independent set problem (MISP) showing that for an n-vertex graph G the sum of the chromatic number of G and the independence number of a graph derived from the complement of G is equal to n. We investigate the applicability of the MISP greedy algorithm to the graph colouring problem. We prove that the well-known Leighton RLF algorithm and an algorithm obtained by modifying the MISP greedy heuristic behave in exactly the same way.
引用
收藏
页码：191 / 200
页数：10
相关论文
共 17 条
[1]   NEW METHODS TO COLOR THE VERTICES OF A GRAPH [J].
BRELAZ, D .
COMMUNICATIONS OF THE ACM, 1979, 22 (04) :251-256
[2]   Cliques, holes and the vertex coloring polytope [J].
Campêlo, M ;
Corrêa, R ;
Frota, Y .
INFORMATION PROCESSING LETTERS, 2004, 89 (04) :159-164
[3]  
CAMPELO M, 2003, 18 INT S MATH PROGR
[4]  
Chaitin G. J., 1982, SIGPLAN Not, V17, P98, DOI [DOI 10.1145/800230.806984, 10.1145/872726. 806984, DOI 10.1145/872726.806984]
[5]  
Culberson JC, 1996, DIMACS SERIES DISCRE, V26, P245
[6]   Zero knowledge and the chromatic number [J].
Feige, U ;
Kilian, J .
ELEVENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 1996, :278-287
[7]   A survey of local search methods for graph coloring [J].
Galinier, P ;
Hertz, A .
COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (09) :2547-2562
[8]   What color is your Jacobian? Graph coloring for computing derivatives [J].
Gebremedhin, AH ;
Manne, F ;
Pothen, A .
SIAM REVIEW, 2005, 47 (04) :629-705
[9]   A new approach to partial constraint satisfaction problems [J].
Gupta, DK ;
Gupta, N .
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2004, 81 (12) :1465-1476
[10]   USING TABU SEARCH TECHNIQUES FOR GRAPH-COLORING [J].
HERTZ, A ;
DEWERRA, D .
COMPUTING, 1987, 39 (04) :345-351
12