A Guide to Graph Colouring: Algorithms and Applications by R.M.R. Lewis

By R.M.R. Lewis

This e-book treats graph colouring as an algorithmic challenge, with a powerful emphasis on functional functions. the writer describes and analyses a few of the best-known algorithms for colouring arbitrary graphs, concentrating on even if those heuristics provides optimum strategies in certain cases; how they practice on graphs the place the chromatic quantity is unknown; and whether or not they can produce larger suggestions than different algorithms for particular types of graphs, and why.


The introductory chapters clarify graph colouring, and limits and optimistic algorithms. the writer then exhibits how complex, smooth ideas might be utilized to vintage real-world operational learn difficulties akin to seating plans, activities scheduling, and collage timetabling. He contains many examples, feedback for extra analyzing, and ancient notes, and the booklet is supplemented by way of an internet site with an internet suite of downloadable code.


The e-book might be of price to researchers, graduate scholars, and practitioners within the components of operations study, theoretical computing device technological know-how, optimization, and computational intelligence. The reader must have user-friendly wisdom of units, matrices, and enumerative combinatorics.

Show description

Read or Download A Guide to Graph Colouring: Algorithms and Applications PDF

Best operations research books

Business Dynamics in Information Technology

Rising company versions, worth configurations, and knowledge applied sciences have interaction over the years to create aggressive virtue. glossy details know-how needs to be studied, understood, and utilized alongside the time size of months and years, the place adjustments are the rule of thumb. Such alterations created through interactions among company parts and assets are rather well fitted to method dynamics modeling.

Hybrid Optimization: The Ten Years of CPAIOR

This quantity makes a speciality of the mixing of synthetic intelligence and constraint programming to unravel difficulties in operations examine and combinatorial optimization. This quantity collects the contributions of specialists from quite a few learn parts together with choice concept, platforms engineering, propositional satisfiability, mathematical optimization, and synthetic intelligence.

Entscheidungsverfahren für komplexe Probleme: Ein heuristischer Ansatz

Das Treffen von Entscheidungen von großer Tragweite bildet die wichtigste Aufgabe von Führungskräften. Es handelt sich dabei um eine schwierige Aufgabe, weil die bedeutsamen Entscheidungen meist auch komplex sind. Das vorliegende Buch stellt ein Entscheidungsverfahren vor, mit dessen Hilfe komplexe Probleme schrittweise bearbeitet werden können.

The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management (Springer Series in Operations Research and Financial Engineering)

Fierce pageant in modern day worldwide marketplace presents a robust motivation for constructing ever extra subtle logistics platforms. This booklet, written for the logistics supervisor and researcher, offers a survey of the fashionable conception and alertness of logistics. The aim of the publication is to offer the state of the art within the technology of logistics administration.

Additional resources for A Guide to Graph Colouring: Algorithms and Applications

Sample text

In the next (n − 2) steps, according to the behaviour of DS ATUR a path of vertices of alternating colours will be constructed that extends from v in both clockwise and anticlockwise directions. At the end of this process, a path comprising n − 1 vertices will have been formed, and a single vertex u will remain that is adjacent to both terminal vertices of this path. If Cn is an even cycle, n − 1 will be odd, meaning that the terminal vertices have the same colour. Hence u can be coloured with the alternative colour.

This gives G REEDY an overall worst-case complexity O(n2 ). In practice, the G REEDY algorithm produces feasible solutions quite quickly; however, these solutions can often be quite poor in terms of the number of colours that the algorithm requires compared to the chromatic number. Consider, for example, the bipartite graph G = (V1 ,V2 , E) in which n is even and where the vertex sets and edge set are defined V1 = {v1 , v3 , . . , vn−1 }, V2 = {v2 , v4 , . . , vn }, and E = {{vi , v j } : vi ∈ V1 ∧ v j ∈ V2 ∧ i + 1 = j} .

If G is not connected, it is enough to consider each component of G separately. For purposes of contradiction assume that one vertex v has a saturation degree of 2, meaning that v has two neighbours, u1 and u2 , assigned to different colours. From these two neighbours we can build two paths which, because G is connected, will have a common vertex u. Hence we have formed a cycle containing vertices v, u1 , u2 , u and perhaps others. Since G is bipartite, the length of this cycle must be even, meaning that the u1 and u2 must have the same colour, contradicting our initial assumption.

Download PDF sample

Rated 4.92 of 5 – based on 13 votes