Function ADS::dsatur

• Defined in File Heuristics.h

Function Documentation

inline std::vector<int> ADS::dsatur(const Adjacency &G)

saturation degree: the color, from 0, of each node of G, colored one at a time with the least color not on its neighbours, the next node the one with most distinct colors among its neighbours, then with most neighbours colored, then the first; O( n^3 )

Pre:

G is unoriented, i.e., square and symmetric

Post:

a proper coloring