# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**83**> 84 85 86 87 88 89 .. 156 >> Next

In the former case a feasible colouring using q2<q 1 colours has been obtained, and by replacing q, by q2 in the above procedure we backtrack again in an attempt to find a colouring using q3 ^q2 — 1 colours; while in the latter case we backtrack again from x( and proceed forward as before. When we eventually seek to backtrack past xlt the algorithm terminates with q as the chromatic number of G, where q is the least integer for which a feasible colouring has been obtained, with the actual colouring being given by the C(Xj) in force at that time.

Example Consider the 7-vertex graph G in Figure 8.3. The sequential

Figure 8.3

The Graph-Colouring Problem 219

values of the C(Xj) assigned to the vertex of G will then be as follows:

C(x2) = 1 C(x2) = 2 C(x3) = 1 C(x4) = 1 C(x5) = 2 C(x6) = 3 C(x7) = 4.

(Thus the first feasible colouring obtained necessitates the use of 4 colours.)

C(x5) = 3 C(x4) = 2 C(x5) = 1 C(x6) = 3 C(xs) = 3 C(x4) = 3 C(x5) = 1 C(x6) = 3

C(x5) = 2 C(x6) = 3

C(x3) = 3 C(x4) = 1 C(xs) = 2 C(x6) = 3

C(x5) = 3 C(x4) = 2C(x5) = 1C(x6) = 3 C(xs) = 3 C(x4) = 3 C(x5) = 1 C(x6) = 3

C(x5) = 2 C(x6) = 3 C(x7) = 1.

Thus a colouring has been found involving only 3 colours, viz. {(x,, x7), (x2, x5), (x3, x4, x6)}, and since no further backtracking possibilities exist, the algorithm terminates, with y(G) = 3.

8.2.1.2 Improvements to the Simple Algorithm

In the presentation given above, we have implicitly made use of the fact that if a vertex x, cannot be coloured with any of the colours used for the previous (i — 1) vertices, then one need only consider the assignment of colour q + 1 to x„ where q = max,«-, {Cfx,)} as the sole alternative for forward branching at this stage. This result, which is formally proved in (Brown, 1972), leads naturally to some limitation of the size of the search tree.

In particular, we know then that the only colour which will be assigned to vertex xt throughout the course of the algorithm will be colour 1. Similarly, the only alternatives which will be considered for vertex x2 will be colours 1 and 2, depending on whether x, and x2 are to have the same or different colours. Thus, if x2 is adjacent to x, (so that they cannot be coloured the same) then the only colour considered for x2 would be colour 2. Repeating this argument, we see that if the vertices xx, x2,.. ., Xp constitute a clique, there will be but one colour assigned to each throughout the course of the algorithm; therefore the algorithm can be terminated when all backtrackings from vertex Xp+1 have been completed, thus again reducing the search.

Recalling that the ordering of the vertices prior to the algorithm was arbitrary, it is then obvious that arranging the vertices so that the first ai(G)

220

Samuel M. Korman

vertices constitute a clique of the graph G will improve the efficiency of the algorithm. A further enhancement is to order the remaining vertices so that, for any i, vertex x, is adjacent to more of the vertices x,, x2,. .., x, ^ than are any of the vertices Xj+1,..., x„ (ties being broken by choosing the vertex of greater degree). Indeed, as this procedure will in general lead to a near-maximum clique anyway, it is reasonable to use this criterion to order all the vertices, with x3 then being a vertex of maximum degree of G.

It is also possible to improve the simple algorithm by using a look-ahead procedure during the course of the algorithm in an effort to reduce the number of backtracking steps, and also to direct the search (Brown, 1972). However, the basic algorithm can be greatly improved by incorporating the concept of a dynamic re-ordering of the as yet uncoloured vertices as the algorithm progresses, so that the vertex to be coloured next (at any stage) is that one, amongst all uncoloured vertices, which has the smallest number of feasible possible colour assignments available to it. This heuristic strategy will then naturally result in a reduction of the size of the total search-tree for the problem, by terminating those forward branchings which do not lead to the optimal solutions at as early a stage as possible (Korman, 1975).

The above procedure is relatively easy to incorporate into the basic algorithm, and in fact, as will be seen from the computational results of Section 8.4, gives rise to a marked reduction in computing times. Moreover, using the vertex re-ordering procedure at each stage will serve a similar purpose as the backtracking criterion of the look-ahead procedure in Brown (1972). Thus, if at any stage of the algorithm there exists some vertex xk which cannot be assigned any colour which is less than qh, where qh is the number of colours in the best colouring to date (so that xk has no possible feasible assignments open to it) then xk will be chosen as the next vertex to be coloured and a backtracking step will immediately ensue.

Table 8.1

Stage Activity P(x3) PM PM P(x4) P(xs) PM PM

0 Initialize 7 P(i) = n Vi 7 1 7 7 7 7

1 C(xd= 1 - 6 7 7 7 6 7

2 C(x2) = 2 — — 6 7 7 5 6

**83**> 84 85 86 87 88 89 .. 156 >> Next