Advertisement
Published in:
2015 | OriginalPaper | Chapter
Incremental MaxSAT Reasoning to Reduce Branches in a Branch-and-Bound Algorithm for MaxClique
Authors : Chu-Min Li, Hua Jiang, Ru-Chu Xu
Published in: Learning and Intelligent Optimization
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
When searching for a maximum clique of a graph using a branch-and-bound algorithm, it is usually believed that one should minimize the set of branching vertices from which search is necessary. It this paper, we propose an approach called incremental MaxSAT reasoning to reduce the set of branching vertices in three ways, developing three algorithms called DoMC (short for Dynamic ordering MaxClique solver), SoMC and SoMC- (short for Static ordering MaxClique solver), respectively. The three algorithms differ only in the way to reduce the set of branching vertices. To our surprise, although DoMC achieves the smallest set of branching vertices, it is significantly worse than SoMC and SoMC-, because it has to change the vertex ordering for branching when reducing the set of branching vertices. SoMC is the best, because it preserves the static vertex ordering for branching and reduces the set of branching vertices more than SoMC-.