RANGE Lab.

(Operations Research, Algorithmics, Networks and Graphs Entity)

Current main research projects

o New models for graph colouring problems

o Modern heuristics for graph colouring problems : adaptive memory, variable neighbourhood search, etc.

o Transformations which preserve the stability number

o New classes of graphs for which the stability number can be found in polynomial time : augmenting graph technique

o Let C be a set of constraints in a given problem. Let S(C) denote the set of feasible solutions induced by C, and suppose that S(C) is empty. We are interested in finding a small subset C’ of C such that S(C’) is also empty. For example, the constraints in a graph colouring problem impose that the endpoints of an edge should have a different colour. If a graph G cannot be coloured with a given number k of colours, we are interested in finding a small partial subgraph of G that is also not k-colourable