@inbook {JH2008b,
title = {Contraction-Based Heuristics to Improve the Efficiency of Algorithms Solving the Graph Colouring Problem},
booktitle = {Studies in Computational Intelligence},
year = {2008},
pages = {167--184},
publisher = {Springer},
organization = {Springer},
type = {incollection},
keywords = {constraint satisfaction, evolutionary computation, graph colouring},
author = {Juhos, I. and van Hemert, J. I.},
editor = {Cotta, C. and van Hemert, J. I.}
}
@conference {JH2006,
title = {Improving Graph Colouring Algorithms and Heuristics Using a Novel Representation},
booktitle = {Springer Lecture Notes on Computer Science},
number = {3906},
year = {2006},
pages = {123--134},
publisher = {Springer-Verlag},
organization = {Springer-Verlag},
type = {inproceedings},
abstract = {We introduce a novel representation for the graph colouring problem, called the Integer Merge Model, which aims to reduce the time complexity of an algorithm. Moreover, our model provides useful information for guiding heuristics as well as a compact description for algorithms. To verify the potential of the model, we use it in dsatur, in an evolutionary algorithm, and in the same evolutionary algorithm extended with heuristics. An empiricial investigation is performed to show an increase in efficiency on two problem suites , a set of practical problem instances and a set of hard problem instances from the phase transition.},
keywords = {constraint satisfaction, graph colouring},
author = {Juhos, I. and van Hemert, J. I.},
editor = {J. Gottlieb and G. Raidl}
}
@article {JH2006a,
title = {Increasing the efficiency of graph colouring algorithms with a representation based on vector operations},
journal = {Journal of Software},
volume = {1},
number = {2},
year = {2006},
pages = {24--33},
type = {article},
abstract = {We introduce a novel representation for the graph colouring problem, called the Integer Merge Model, which aims to reduce the time complexity of graph colouring algorithms. Moreover, this model provides useful information to aid in the creation of heuristics that can make the colouring process even faster. It also serves as a compact definition for the description of graph colouring algorithms. To verify the potential of the model, we use it in the complete algorithm DSATUR, and in two version of an incomplete approximation algorithm; an evolutionary algorithm and the same evolutionary algorithm extended with guiding heuristics. Both theoretical and empirical results are provided investigation is performed to show an increase in the efficiency of solving graph colouring problems. Two problem suites were used for the empirical evidence: a set of practical problem instances and a set of hard problem instances from the phase transition.},
keywords = {graph colouring},
author = {Juhos, I. and van Hemert, J. I.}
}
@conference {JTH2005,
title = {Heuristic Colour Assignment Strategies for Merge Models in Graph Colouring},
booktitle = {Springer Lecture Notes on Computer Science},
year = {2005},
pages = {132--143},
publisher = {Springer-Verlag, Berlin},
organization = {Springer-Verlag, Berlin},
type = {inproceedings},
abstract = {In this paper, we combine a powerful representation for graph colouring problems with different heuristic strategies for colour assignment. Our novel strategies employ heuristics that exploit information about the partial colouring in an aim to improve performance. An evolutionary algorithm is used to drive the search. We compare the different strategies to each other on several very hard benchmarks and on generated problem instances, and show where the novel strategies improve the efficiency.},
keywords = {constraint satisfaction, graph colouring},
author = {Juhos, I. and T{\'o}th, A. and van Hemert, J. I.},
editor = {G. Raidl and J. Gottlieb}
}
@conference {JTH2004,
title = {Binary Merge Model Representation of the Graph Colouring Problem},
booktitle = {Springer Lecture Notes on Computer Science},
number = {3004},
year = {2004},
pages = {124--134},
publisher = {Springer-Verlag, Berlin},
organization = {Springer-Verlag, Berlin},
type = {inproceedings},
abstract = {This paper describes a novel representation and ordering model that aided by an evolutionary algorithm, is used in solving the graph \emph{k}-colouring problem. Its strength lies in reducing the search space by breaking symmetry. An empirical comparison is made with two other algorithms on a standard suit of problem instances and on a suit of instances in the phase transition where it shows promising results.},
keywords = {constraint satisfaction, graph colouring},
isbn = {3-540-21367-8},
author = {Juhos, I. and T{\'o}th, A. and van Hemert, J. I.},
editor = {J. Gottlieb and G. Raidl}
}
@conference {JTTTH2003,
title = {A new permutation model for solving the graph k-coloring problem},
booktitle = {Kalm{\`a}r Workshop on Logic and Computer Science},
year = {2003},
pages = {189--199},
type = {inproceedings},
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.},
keywords = {constraint satisfaction, graph colouring},
author = {Juhos, I. and T{\'o}th, A. and Tezuka, M. and Tann, P. and van Hemert, J. I.}
}