6533b85bfe1ef96bd12bb34a

RESEARCH PRODUCT

A Modified Tabu Thresholding Approach for the Generalised Restricted Vertex Colouring Problem

M. Angeles PerezM. Sacramento QuintanillaVicente Valls

subject

Vertex (graph theory)Mathematical optimizationComputer scienceBounded functionGraph colouringState (functional analysis)Evaluation functionThresholding

description

We present a modification of the Tabu Thresholding (TT) approach and apply it to the solution of the generalised restricted vertex colouring problem. Both the bounded and unbounded cases are treated. In our algorithms, the basic TT elements are supplemented with an evaluation function that depends on the best solution obtained so far, together with a mechanism which reinforces the aggressive search in the improving phase, and new diversification strategies which depend on the state of the search. The procedure is illustrated through the solution of the problem of minimising the number of workers in a heterogeneous workforce.

yearjournalcountryeditionlanguage
1996-01-01
https://doi.org/10.1007/978-1-4613-1361-8_32