An efficient branch-and-bound algorithm based on MaxSAT for the maximum clique problem
作者： Chu-Min Li , Zhe Quan
DOI:
关键词:
摘要: … MaxSAT problem asks to find an assignment satisfying all the hard clauses and maximizing the number of satisfied soft clauses… recursive calls by choosing a branching vertex, eg v1: …
参考文章(12)
Felip Manyà, Jordi Planes, Chu-Min Li, Detecting disjoint inconsistent subformulas for computing lower bounds for Max-SAT national conference on artificial intelligence. pp. 86- 91 ,(2006)
Randy Carraghan, Panos M. Pardalos, An exact algorithm for the maximum clique problem Operations Research Letters. ,vol. 9, pp. 375- 382 ,(1990) , 10.1016/0167-6377(90)90057-C
Patric R.J. Östergård, A fast algorithm for the maximum clique problem Discrete Applied Mathematics. ,vol. 120, pp. 197- 207 ,(2002) , 10.1016/S0166-218X(01)00290-6
Immanuel M. Bomze, Marco Budinich, Panos M. Pardalos, Marcello Pelillo, The maximum clique problem Journal of Global Optimization. ,vol. 4, pp. 1- 74 ,(1994) , 10.1007/978-1-4757-3023-4_1
Etsuji Tomita, Tomokazu Seki, An efficient branch-and-bound algorithm for finding a maximum clique Lecture Notes in Computer Science. ,vol. 2731, pp. 278- 289 ,(2003) , 10.1007/3-540-45066-1_22
W. Pullan, H. H. Hoos, Dynamic local search for the maximum clique problem Journal of Artificial Intelligence Research. ,vol. 25, pp. 159- 185 ,(2006) , 10.1613/JAIR.1815
C. M. Li, F. Manya, J. Planes, New inference rules for Max-SAT Journal of Artificial Intelligence Research. ,vol. 30, pp. 321- 359 ,(2007) , 10.1613/JAIR.2215
Etsuji Tomita, Toshikatsu Kameda, An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments Journal of Global Optimization. ,vol. 37, pp. 311- 311 ,(2007) , 10.1007/S10898-006-9039-7
F. Heras, J. Larrosa, A. Oliveras, MiniMaxSAT: An Efficient Weighted Max-SAT solver Journal of Artificial Intelligence Research. ,vol. 31, pp. 1- 32 ,(2008) , 10.1613/JAIR.2347
Janez Konc, Dusanka Janezic, An improved branch and bound algorithm for the maximum clique problem ,(2007)