Coloring Graphs With a General Heuristic Search Engine

Vinhthuy Phan Steven Skiena

To appear at Computational Symposium on Graph Coloring and Generalizations (COLOR02), Ithaca, NY, 7-8 September 2002


In this paper, we report on our experiences building implementations of vertex coloring and graph bandwidth coloring with {\em Discropt}. We use the same problem-independent heuristic implementations reported in \cite{PPS-alenex02} without fundamental changes or problem-specific tuning. Adapting our heuristics to graph coloring problems provides a good test of the flexibility of our system for two reasons. First, graph coloring is well known as a very challenging problem for local search heuristics such as employed within our system. Second, the fundamental solution representation for graph colorings (set partitions) had not been implemented in our system as of \cite{PPS-alenex02}. In this paper, we test the performance of optimization routines developed for permutation and subgraph problems on a completely different class of object.

Server START Conference Manager
Update Time 23 Jul 2002 at 13:35:57
Start Conference Manager
Conference Systems