FINDING MAXIMUM CLIQUES IN ARBITRARY AND IN SPECIAL GRAPHS

The classical problem of finding a clique of largest cardinality in an arbitrary graph is NP-complete. For that reason earlier work diverges into two directions. The first concerns algorithms solving the problem for arbitrary graphs in reasonable (but exponential) time, the other restricts to special classes of graphs where polynomial methods can be found. Here, the two directions are combined in a way. A branch and bound algorithm is developed treating the general case. Computational experiments on random graphs show that this algorithm compares favorable to the fastest known method. Furthermore, it consumes only polynomial time for quite a few graph classes. For some of them no polynomial solution method is given so far.