Pseudocode.docx

BronKerbosch1(R, P, X): if P and X are both empty: report R as a maximal clique for each vertex v in P: BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v)) P := P \ {v} X := X ⋃ {v}

Greedy To start, the algorithm takes an empty solution S and a permutation of the π. In each outer loop the algorithm takes the ith vertex in the permutation, πi , and attempts to find a colour class Sj ∈ S into which it can be inserted. If such a colour class currently exists in S,

then the vertex is added to it and the process moves on to consider the next vertex π i+1 . If not, the algorithm creates a new colour class for the vertex. DSatur The algorithm is basically the same as greedy. But we have a set X which holds the uncolored vertices. And at each loop, the next vertice is choosen from the set based on the saturation degree. The saturation degree is the caculated as the number of colored vertice neighbors from the uncolored Vertice. The one with the highest saturation degree is chosen.

Welsh Power The algorithm arranges the traversing order according to the degree of the vertice in descending order. Then each vertice is taken out and tried to color in the same color. If it has no clash with the currently colored vertices, then it is colored. All the uncolored go through the same process, while using the next color in the next round until no uncolored is left. Bron-Kerbosch 1.Take any single vertex in graph as a subset(uses set R) 2.Add as many vertices to this subset(which are adjacent to every other vertex in it), as possible. (uses sets R, P) 3.If subset is not already reported, report as maximal clique(uses set X) 4.Remove the vertice used in step 1 from further considerations 5.Repeat step 1 to 4 for all vertices in graph