A new permutation model for solving the graph k-coloring problem (bibtex)

by I Juhos, A Tóth, M Tezuka, P Tann and van Hemert, J

Abstract:

This paper describes a novel representation and ordering model, that is aided by an evolutionary algorithm, is used in solving the graph k-coloring. A comparison is made between the new representation and an improved version of the traditional graph coloring technique DSATUR on an extensive list of graph k-coloring problem instances with different properties. The results show that our model outperforms the improved DSATUR on most of the problem instances.

Reference:

A new permutation model for solving the graph k-coloring problem (I Juhos, A Tóth, M Tezuka, P Tann and van Hemert, J), In Kalmàr Workshop on Logic and Computer Science, 2003.

Bibtex Entry:

@inproceedings{JTTTH2003,
	_address = {Szeged, Hungary},
	_day = {01},
	abstract = {This paper describes a novel representation and ordering model, that is aided by an evolutionary algorithm, is used in solving the graph k-coloring. A comparison is made between the new representation and an improved version of the traditional graph coloring technique DSATUR on an extensive list of graph k-coloring problem instances with different properties. The results show that our model outperforms the improved DSATUR on most of the problem instances.},
	author = {I Juhos and A T{\'o}th and M Tezuka and P Tann and van Hemert, J},
	booktitle = {Kalm{\`a}r Workshop on Logic and Computer Science},
	date-added = {2008-08-18 12:44:11 +0100},
	date-modified = {2008-08-18 12:44:11 +0100},
	keywords = {constraint satisfaction; graph colouring},
	pages = {189--199},
	pdf = {http://www.vanhemert.co.uk/publications/kalmar2003.A_new_permutation_model_for_solving_the_graph_k-coloring_problem.pdf},
	title = {A new permutation model for solving the graph k-coloring problem},
	year = {2003}}