Combining Efficient Preprocessing and Incremental MaxSAT Reasoning for MaxClique in Large Graphs
Hua Jiang, Chu-Min Li, Felip Manyà · Frontiers in artificial intelligence and applications · 2016
We describe a new exact algorithm for MaxClique, called LMC (short for Large MaxClique), that is especially suited for large sparse graphs. LMC is competitive because it combines an efficient preprocessing procedure and incremental MaxSAT reasoning in a branch-and-bound scheme. The empirical results show that LMC outperforms existing exact MaxClique algorithms on large sparse graphs from real-world applications.