Keywords: maximum-weight clique, branch and bound algorithm, maximum-weight independent set, vertex-colouring, graph, maximum clique.

In this paper a new algorithm for finding the maximum-weight clique is introduced. This algorithm is based on a heuristic vertex-colouring and a backtrack search. Colour classes found in the heuristic vertex-colouring are used to prune branches of the maximum-weight clique search tree - since vertices of the same colour class cannot participate in the same maximum clique. Basing on that classes algorithm can more effectively define when the current subgraph can contain a larger clique than already found or not than by just looking at the number of vertices of this subgraph.

A degree of a subgraph will be calculated as a sum of maximum weights of each colour class existing on this subgraph: for each existing class the algorithm have to find a vertex of the maximum-weight and then sum up weights of those vertices.

The pruning formula on a subgraph G_d is the next: If w1+Degree(G_d less or equal than CBC, where CBC is a size of the current best clique then we prune and w is already accumulated weight of the forming maximum clique.

A backtrack search is also proved to be effective information capture and branches pruning strategy (originally it was shown by Östergård [1]). Those two pruning strategies provided us with a very fast algorithm for the maximum-weight clique determination: ten times faster than Östergård's one. The algorithm is also very easy to implement. Probably the triviality of ideas makes it so fast. Another advantage is a way how the heuristic result is used for determining the exact result: usually a heuristic result just sets upper or lower bounds, which are quite quickly replaced by a current best result. In the new algorithm a heuristic vertex-colouring is employed on the permanent base through the whole algorithm's work. Moreover, the algorithm can evaluate without changes in algorithm's core steps by just inventing a new and more effective heuristic algorithm for the vertex colouring. The lesser colour-classes we have the more effectively we prune branches of a search tree. Quite effective results of the new algorithm were reached not on the best splitting vertices into colour classes. The number of colour classes approximately larger by 50%-25% than size of the maximum clique.

1

P.R.J. Östergård, "A new algorithm for the maximum-weight clique problem", Nordic Journal of Computing, 8, 424-436, 2001.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)