DSatur
DSatur is a graph colouring algorithm put forward by Daniel Brélaz in 1979.[1] Similarly to the greedy colouring algorithm, DSatur colours the vertices of a graph one after another, expending a previously unused colour when needed. Once a new vertex has been coloured, the algorithm determines which of the remaining uncoloured vertices has the highest number of colours in its neighbourhood and colours this vertex next. Brélaz defines this number as the degree of saturation of a given vertex.[1] The contraction of the degree of saturation forms the name of the algorithm.[2]: 39 DSatur is a heuristic graph colouring algorithm, yet produces exact results for bipartite,[1] cycle, and wheel graphs.[2] DSatur has also been referred to as saturation LF in the literature.[3]
Pseudocode
Define the degree of saturation of a vertex as the number of different colours in its neighbourhood. Given a simple, undirected graph G compromising vertex set V and edge set E:[4]
- Generate a degree ordering of V.
- Select a vertex of maximal degree and colour it with the first colour.
- Consider a vertex with the highest degree of saturation. Break ties by considering that vertex with the highest degree. Further ties are broken randomly.
- Loop through the colour classes created so far, and colour the selected vertex with the first suitable colour.
- Unless V is all coloured, return to step 3.
Performance
The worst-case complexity of DSatur is Ο(n2), however in practical some additional expenses result from the need for holding the degree of saturation of the uncoloured vertices.[2] DSatur has been proven to be exact for bipartite graphs,[1] as well as for cycle and wheel graphs.[2] In an empirical comparison by Lewis 2015, DSatur produced significantly better vertex colourings than the greedy algorithm on random graphs with edge probability p = 0.5 at varying number of vertices, while in turn producing significantly worse colourings than the Recursive Largest First algorithm.
References
- ^ a b c d Brélaz, Daniel (1979-04-01). "New methods to color the vertices of a graph". Communications of the ACM. 22 (4): 251–256. doi:10.1145/359094.359101. ISSN 0001-0782.
- ^ a b c d Lewis, R.M.R. (2016). A Guide to Graph Colouring. Berlin: Springer. doi:10.1007/978-3-319-25730-3. ISBN 978-3-319-25728-0.
- ^ Kubale, ed. (2004). Graph Colorings (Vol.352). Providence: American Mathematical Society. p. 13. ISBN 978-0-8218-3458-9.
- ^ Lewis, Rhyd (2019-01-19). "Constructive Algorithms for Graph Colouring". youtube.com. Event occurs at 3:49.