Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/23114
Title: Metaheuristics for robust graph coloring
Authors: Wang, F
Xu, Z 
Keywords: Metaheuristics
Robust graph coloring
Unconstrained quadratic programming
Issue Date: 2011
Publisher: Springer
Source: Journal of heuristics, 2011, p. 1-20 How to cite?
Journal: Journal of Heuristics 
Abstract: This paper studies a robust graph coloring problem, which is a variant of the classical graph coloring problem, where penalties are charged for non-adjacent vertices that are assigned the same color. The problem can be formulated as an unconstrained quadratic programming problem, and has many applications in industry. Since the problem is known to be strongly NP-complete, we develop a number of metaheuristics for it, which are based on various encoding schemes, neighborhood structures, and search algorithms. Extensive experiments suggest that our metaheuristics with a partition based encoding scheme and an improvement graph based neighborhood outperform other methods tested in our study.
URI: http://hdl.handle.net/10397/23114
ISSN: 1381-1231
DOI: 10.1007/s10732-011-9180-4
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

7
Last Week
0
Last month
1
Citations as of Oct 11, 2017

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
0
Citations as of Oct 16, 2017

Page view(s)

55
Last Week
8
Last month
Checked on Oct 23, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.