Constrained Bandwidth Multicoloration Neighbourhoods

Steven Prestwich

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


A combination of local search and constraint propagation called FCNS has previously been described for pure graph colouring. FCNS is a hybrid of the DSATUR backtracker and the IMPASSE local search algorithm, restricting coloration neighbourhoods by propagation, and dynamically ordering vertices by the Brelaz heuristic. We extend it to bandwidth colouring and present results on a set of geometric graphs. A related algorithm called Saturn has previously been described for pure 0/1 integer linear programs. We model bandwidth multicolouring as an ILP and present Saturn results on the same graphs. An assessment of performance is postponed until other results are presented at the symposium.

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