“Draft:DSatur”的意思、由来-开放百科全书

词条

Draft:DSatur

释义

Pseudocode
Performance
References

DSatur is a graph colouring algorithm put forward by Daniel Brélaz in 1979.^[1]Similarly to the GREEDY 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]{{rp|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 randomnly.
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 Ο(n²), 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

1. ^¹²³{{Cite journal|last=Brélaz|first=Daniel|date=1979-04-01|title=New methods to color the vertices of a graph|journal=Communications of the ACM|volume=22|issue=4|pages=251–256|doi=10.1145/359094.359101|issn=0001-0782}}
2. ^¹²³{{Cite book|title=A Guide to Graph Colouring|last=Lewis|first=R.M.R.|publisher=Springer|year=2016|isbn=978-3-319-25728-0|location=Berlin|pages=|doi=10.1007/978-3-319-25730-3}}
3. ^{{Cite book|title=Graph Colorings (Vol.352)|last=|first=|publisher=American Mathematical Society|year=2004|isbn=978-0-8218-3458-9|editor-last=Kubale|location=Providence|pages=13}}
4. ^{{Cite web|url=https://www.youtube.com/watch?v=L2csXWQMsNg|title=Constructive Algorithms for Graph Colouring|last=Lewis|first=Rhyd|date=2019-01-19|website=youtube.com|archive-url=|archive-date=|dead-url=|access-date=|time=3:49}}

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。