Greedy Algorithms and the Maximum Clique Problem

In the current (November 2011) issue of MSDN Magazine I have an article that describes an advanced algorithm to solve the maximum clique problem. In simplified terms, if you have a graph structure, the goal of the maximum clique problem is to find the largest group of nodes in the graph that are all connected to each other. The maximum clique problem has been around for many years and actually has quite a few important applications. For example, if the graph represents a social network, knowing large cliques could be useful to advertisers to get the most bang for their buck. The maximum clique problem is extremely challenging for large graphs. The algorithm I describe in the MSDN Magazine article uses a greedy approach. You start with a random node in the graph. Then from all adjacent nodes to the start node, select the “best” node and add it to the growing clique. Then, from all nodes which are adjacent to the first two nodes in the clique, select the best node and add it. The process is repeated until you can’t add any more nodes that are connected to all nodes in the clique. The definition of “best” is the key to greedy algorithms. You can read the article at:

This entry was posted in Software Test Automation. Bookmark the permalink.