Welsh Powell Algorithm
The Welsh Powell algorithm is an algorithm used for graph coloring. Graph coloring usually deals with undirected graphs.
What is graph coloring?
Graph coloring is the process of assigning colors (usually in the form of integers) so that no two adjacent nodes have the same color. Most of the time, the idea is to minimize the number of different colors needed to color the entire graph. The number of colors needed to color a graph is called the chromatic number.
The notation from chromatic number is ϗ(G) = minimum number of colors needed.
Steps for doing the Welsh Powell algorithm:
Preprocessing:
First, traverse the graph and get the degree of each node. The degree of a node is how many edges are attached to it. Then, sort the degrees in non-decreasing order. So, the nodes with the highest degree come first.
Assigning color:
Start with the first item in the non-decreasing degree list and give it a color. Then traverse the rest of the graph, assigning the color and making sure it is not adjacent to any of the same color.
It is important to remember that if node 1 is the same color as non-adjacent node 3, Any other nodes of the same color have to be non-adjacent to both node 1 and node 3.
As nodes are colored, it’s important to mark them off as used so the algorithm doesn’t come back to them later.
Once, all possible cells are assigned color 1. It’s time to go back into the list and find the highest-degree node that hasn’t already been assigned a color. The process of finding the highest-degree node and marking nodes will continue until there are no more nodes left.
In the end, the algorithm would have created the optimal graph coloring.
Welsh Powell Time complexity:
Welsh Powell on normal graphs O(n^2)
Welsh Powell on bipartite graph O(n)