An Exact Algorithm for Solving the Maximum Weighted Clique Problem with Using Comparability Supergraphs

摘要

We show a method for calculating the upper bound of the weight of the maximum weighted clique problem with using comparability supergraphs. With our method, many algorithms for the maximum cadinality clique problem with using the branch-and-bound technique based on coloring are naturally extended to algorithms for the maximum weighted clique problem. Our method uses the maximum weighted clique in a comparability supergraph of the given graph at the bounding stage. We investigate the efficiency and the problems of our method some with some computational experiments.