Combining efficient preprocessing and incremental MaxSAT reasoning for MaxClique in large graphs
作者： Felip Manyà , Chu-Min Li , Hua Jiang
DOI: 10.3233/978-1-61499-672-9-939
关键词:
摘要: We describe a new exact algorithm for MaxClique, called LMC (short Large MaxClique), that is especially suited large sparse graphs. competitive because it combines an efficient preprocessing procedure and incremental MaxSAT reasoning in branch-and-bound scheme. The empirical results show outperforms existing MaxClique algorithms on graphs from real-world applications.
sci-hub.st 参考文章(29)
Chu Min Li, Felip Manya, None, MaxSAT, Hard and Soft Constraints Handbook of Satisfiability. pp. 613- 631 ,(2009) , 10.3233/978-1-58603-929-5-613
Pablo San Segundo, Alvaro Lopez, Panos M. Pardalos, A new exact maximum clique algorithm for large and massive sparse graphs Computers & Operations Research. ,vol. 66, pp. 81- 94 ,(2016) , 10.1016/J.COR.2015.07.013
Chu-Min Li, Zhe Quan, An efficient branch-and-bound algorithm based on MaxSAT for the maximum clique problem national conference on artificial intelligence. pp. 128- 133 ,(2010)
Etsuji Tomita, Yoichi Sutani, Takanori Higashi, Shinya Takahashi, Mitsuo Wakatsuki, A simple and faster branch-and-bound algorithm for finding a maximum clique international symposium on algorithms and computation. pp. 191- 203 ,(2010) , 10.1007/978-3-642-11440-3_18
Matjaz Zaversnik, Vladimir Batagelj, An O(m) Algorithm for Cores Decomposition of Networks arXiv: Data Structures and Algorithms. ,(2003)
Assefaw H. Gebremedhin, Ryan A. Rossi, David F. Gleich, Md. Mostofa Ali Patwary, Parallel Maximum Clique Algorithms with Applications to Network Analysis and Storage arXiv: Social and Information Networks. ,(2013)
Una Benlic, Jin-Kao Hao, Breakout Local Search for maximum clique problems Computers & Operations Research. ,vol. 40, pp. 192- 206 ,(2013) , 10.1016/J.COR.2012.06.002
Chu-Min Li, Zhiwen Fang, Ke Xu, Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem international conference on tools with artificial intelligence. pp. 939- 946 ,(2013) , 10.1109/ICTAI.2013.143
Andrea Grosso, Marco Locatelli, Wayne Pullan, Simple ingredients leading to very efficient heuristics for the maximum clique problem Journal of Heuristics. ,vol. 14, pp. 587- 612 ,(2008) , 10.1007/S10732-007-9055-X
Pablo San Segundo, Fernando Matia, Diego Rodriguez-Losada, Miguel Hernando, An improved bit parallel exact maximum clique algorithm Optimization Letters. ,vol. 7, pp. 467- 479 ,(2013) , 10.1007/S11590-011-0431-Y