Vertex Descent is a local search algorithm which forms the basis of a wide spectrum of tabu search, simulated annealing and hybrid evolutionary algorithms for graph colouring. These algorithms are usually treated as experimental and provide strong results on established benchmarks. As a step towards studying these heuristics analytically, an analysis of the behaviour of Vertex Descent is provided. It is shown that Vertex Descent is able to find feasible colourings for several types of instances in expected polynomial time. This includes 2-colouring of paths and 3-colouring of graphs with maximum degree 3. The same also holds for 3-colouring of a subset of 3-colourable graphs with maximum degree 4. As a consequence, Vertex Descent finds a 3-colouring in expected polynomial time for the smallest graph for which Br 'elaz's heuristic DSATUR needs 4 colours. On the other hand, Vertex Descent may fail for forests with maximum degree 3 with high probability.
Most of the modern graph colouring heuristics are . Currently, the most successful algorithms include a QACol @cite_20 @cite_12 , an algorithm IE @math Col, based on of independent sets @cite_35 and a HEAD with a very small population of two colourings @cite_5 . All three of these algorithms use Vertex Descent combined with several different ideas. These include solution populations, tabu lists, thermal and quantum fluctuations, partition crossovers and preprocessing. However, Vertex Descent remains at the core of all these approaches.
@cite_35 @cite_5 @cite_12 @cite_20
2121391146 2064850189 2068179205 1485830228
This paper presents an effective memetic approach (HEAD ) designed for coloring difficult graphs. In this algorithm a powerful tabu search is used inside a very specific population of individuals. Indeed, the main characteristic of (HEAD ) is to work with a population of only two individuals. This provides a very simple algorithm with neither selection operator nor replacement strategy. Because of its simplicity, (HEAD ) allows an easy way for managing the diversity. We focus this work on the impact of this diversity management on well-studied graphs of the DIMACS challenge benchmarks, known to be very difficult to solve. A detailed analysis is provided for three graphs on which (HEAD ) finds a legal coloring with less colors than reference algorithms: DSJC500.5 with 47 colors, DSJC1000.5 with 82 colors and flat1000_76_0 with 81 colors. The analysis performed in this work will allow to improve (HEAD ) efficiency in terms of computation time and maybe to decrease the number of needed colors for other graphs. Graph coloring is one of the most studied combinatorial optimization problems. This paper presents an improved extraction and expansion method (IE^2COL), initially introduced in Wu and Hao (2012) [44]. IE^2COL employs a forward independent set extraction strategy to reduce the initial graph G. From the reduced graph, IE^2COL triggers a backward coloring process which uses extracted independent sets as new color classes for intermediate subgraph coloring. The proposed method is assessed on 20 large benchmark graphs with 900 to 4000 vertices. Computational results show that it provides new upper bounds for 6 graphs and consistently matches the current best-known results for 12 other graphs. This paper describes a randomised algorithm for the NP-complete problem of 3-colouring the vertices of a graph. The method is based on a model of repulsion in interacting particle systems. Although it seems to work well on most random inputs there is a critical phenomenon apparent reminiscent of critical behaviour in other areas of statistical mechanics. This paper reports on a simple, decentralized, anytime, stochastic, soft graph-colouring algorithm. The algorithm is designed to quickly reduce the number of colour conflicts in large, sparse graphs in a scalable, robust, low-cost manner. The algorithm is experimentally evaluated in a framework motivated by its application to resource coordination in large, distributed networks.