An analysis of solution properties of the graph coloring problem

被引：0

作者：

Hamiez, JP ^{[1
]}

Hao, JK ^{[1
]}

机构：

[1] Ecole Mines Ales, LGI2P, F-30035 Nimes 01, France

来源：

METAHEURISTICS: COMPUTER DECISION-MAKING | 2004年 / 86卷

关键词：

graph coloring; solution analysis; representative sets; tabu search;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper concerns the analysis of solution properties of the Graph Coloring Problem. For this purpose, we introduce a property based on the notion of representative sets which are sets of vertices that are always colored the same in a set of solutions. Experimental results on well-studied DIMACS graphs show that many of them contain such sets and give interesting information about the diversity of the solutions. We also show how such an analysis may be used to improve a tabu search algorithm.

引用

页码：325 / 345

页数：21

共 35 条

[1]

[Anonymous], 1997, Tabu Search

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3]

[Anonymous], 1991, Handbook of genetic algorithms

[4]

[Anonymous], 1993, FDN CONSTRAINT SATIS

[5] Emergence of scaling in random networks [J].

Barabási, AL ;

Albert, R .

SCIENCE, 1999, 286 (5439) :509-512

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

BRELAZ, D .

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

[7]

Cheeseman P., 1991, PROC 12 IJCAI, P331, DOI [DOI 10.5555/1631171.1631221, 10.5555/1631171.1631221]

[8]

CULBERSON JC, 1999, APES131999

[9]

Dorne R, 1998, LECT NOTES COMPUT SC, V1498, P745, DOI 10.1007/BFb0056916

[10]

Dorne R., 1998, METAHEURISTICS ADV T, P77

← 1 2 3 4 →