Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem

摘要: Recently, MaxSAT reasoning has been shown to be powerful in computing upper bounds for the cardinality of a maximum clique graph. However, existing based on have two drawbacks: (1)at every node search tree, performed from scratch compute an bound and is time-consuming, (2) due NP-hardness problem, generally cannot complete at anode may not give tight enough pruning space. In this paper, we propose incremental combine it with remedy drawbacks. The new approach used develop efficient branch-and-bound algorithm MaxClique, called IncMaxCLQ. We conduct experiments show complementarity compare IncMaxCLQ several state-of-the-art algorithms MaxClique.