{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:53:32Z","timestamp":1725512012664},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797180"},{"type":"electronic","value":"9783540797197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79719-7_13","type":"book-chapter","created":{"date-parts":[[2008,5,6]],"date-time":"2008-05-06T04:04:57Z","timestamp":1210046697000},"page":"139-152","source":"Crossref","is-referenced-by-count":3,"title":["A Max-SAT Inference-Based Pre-processing for Max-Clique"],"prefix":"10.1007","author":[{"given":"Federico","family":"Heras","sequence":"first","affiliation":[]},{"given":"Javier","family":"Larrosa","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"13_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/11499107_27","volume-title":"Theory and Applications of Satisfiability Testing","author":"T. Alsinet","year":"2005","unstructured":"Alsinet, T., Many\u00e0, F., Planes, J.: Improved exact solvers for weighted Max-SAT. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol.\u00a03569, pp. 371\u2013377. Springer, Heidelberg (2005)"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Argelich, J., Li, C.M., Many\u00e1, F., Planes, J.: The first and second max-sat evaluations. Journal on Satisfiability, Boolean Modeling and Computation (to appear, 2008)","DOI":"10.3233\/SAT190047"},{"issue":"4","key":"13_CR3","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1137\/0215075","volume":"15","author":"E. Balas","year":"1986","unstructured":"Balas, E., Yu, C.S.: Finding a maximum clique in an arbitrary graph. SIAM Journal of Computation\u00a015(4), 1054\u20131068 (1986)","journal-title":"SIAM Journal of Computation"},{"issue":"8-9","key":"13_CR4","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1016\/j.artint.2007.03.001","volume":"171","author":"M.L. Bonet","year":"2007","unstructured":"Bonet, M.L., Levy, J., Many\u00e0, F.: Resolution for max-sat. Artificial Intelligence\u00a0171(8-9), 606\u2013618 (2007)","journal-title":"Artificial Intelligence"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"S.B.: A new trust region technique for the maximum weight clique problem. Discrete Applied Mathematics 154(15), 2080\u20132096 (2006)","DOI":"10.1016\/j.dam.2005.04.010"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/0167-6377(90)90057-C","volume":"9","author":"R. Carraghan","year":"1990","unstructured":"Carraghan, R., Pardalos, P.: An exact algorithm for the maximum clique problem. Operations Research Letters\u00a09, 375\u2013382 (1990)","journal-title":"Operations Research Letters"},{"key":"13_CR7","unstructured":"Cooper, M.C., de Givry, S., Schiex, T.: Optimal soft arc consistency. In: Proceedings of IJCAI, pp. 68\u201373 (2007)"},{"key":"13_CR8","unstructured":"de Givry, S., Heras, F., Larrosa, J., Zytnicki, M.: Existential arc consistency: getting closer to full arc consistency in weighted csps. In: Proceedings of IJCAI (2005)"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/978-3-540-45193-8_25","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"S. Givry de","year":"2003","unstructured":"de Givry, S., Larrosa, J., Meseguer, P., Schiex, T.: Solving max-sat as weighted csp. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 363\u2013376. Springer, Heidelberg (2003)"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1287\/opre.1040.0189","volume":"53","author":"E. Barnes","year":"2005","unstructured":"Barnes, E., Strickland, D.M., Sokol, J.S.: Optimal protein structure alignment using maximum cliques. Operations Research\u00a053, 389\u2013402 (2005)","journal-title":"Operations Research"},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/3-540-45749-6_44","volume-title":"Algorithms - ESA 2002","author":"T. Fahle","year":"2002","unstructured":"Fahle, T.: Simple and fast: Improving a branch-and-bound algorithm for maximum clique. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 485\u2013498. Springer, Heidelberg (2002)"},{"key":"13_CR12","unstructured":"Heras, F., Larrosa, J.: New inference rules for efficient max-sat solving. In: AAAI (2006)"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-72788-0_8","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2007","author":"F. Heras","year":"2007","unstructured":"Heras, F., Larrosa, J., Oliveras, A.: Minimaxsat: A new weighted max-sat solver. In: Marques-Silva, J., Sakallah, K.A. (eds.) SAT 2007. LNCS, vol.\u00a04501, pp. 41\u201355. Springer, Heidelberg (2007)"},{"issue":"10","key":"13_CR14","doi-asserted-by":"publisher","first-page":"1603","DOI":"10.1093\/bioinformatics\/bth131","volume":"20","author":"Y. Ji","year":"2004","unstructured":"Ji, Y., Xu, X., Stormo, G.D.: A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences. Bioinformatics\u00a020(10), 1603\u20131611 (2004)","journal-title":"Bioinformatics"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., Trick, M.: Second DIMACS implementation challenge: cliques, coloring and satisfiability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a026, AMS (1996)","DOI":"10.1090\/dimacs\/026"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Larrosa, J., Heras, F., de Givry, S.: A logical approach to efficient Max-SAT solving. Artificial Intelligence, an international journal\u00a0172, 204\u2013233","DOI":"10.1016\/j.artint.2007.05.006"},{"issue":"1-2","key":"13_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2004.05.004","volume":"159","author":"J. Larrosa","year":"2004","unstructured":"Larrosa, J., Schiex, T.: Solving weighted csp by maintaining arc-consistency. Artificial Intelligence\u00a0159(1-2), 1\u201326 (2004)","journal-title":"Artificial Intelligence"},{"key":"13_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/11564751_31","volume-title":"Principles and Practice of Constraint Programming - CP 2005","author":"C.M. Li","year":"2005","unstructured":"Li, C.M., Many\u00e0, F., Planes, J.: Exploiting unit propagation to compute lower bounds in branch and bound Max-SAT solvers. In: van Beek, P. (ed.) CP 2005. LNCS, vol.\u00a03709, pp. 403\u2013414. Springer, Heidelberg (2005)"},{"key":"13_CR19","unstructured":"Li, C.M., Manya, F., Planes, J.: Detecting disjoint inconsistent subformulas for computing lower bounds for Max-SAT. In: Proceedings of AAAI (2006)"},{"key":"13_CR20","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1613\/jair.2215","volume":"30","author":"C.M. Li","year":"2007","unstructured":"Li, C.M., Many\u00e0, F., Planes, J.: New inference rules for max-sat. Journal of Artificial Intelligence Research\u00a030, 321\u2013359 (2007)","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1","key":"13_CR21","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/jagm.2000.1075","volume":"36","author":"R. Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: New upper bounds for maximum satisfiability. Journal of Algorithms\u00a036(1), 63\u201388 (2000)","journal-title":"Journal of Algorithms"},{"key":"13_CR22","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(01)00290-6","volume":"120","author":"P.R.J. Ostergard","year":"2002","unstructured":"Ostergard, P.R.J.: A fast algorithm for the maximum clique problem. Discrete Applied Mathematics\u00a0120, 197\u2013207 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"13_CR23","unstructured":"Pevzner, P.A., Sze, S.: Combinatorial approaches to finding subtle signals in DNA sequences. In: ISMB, pp. 269\u2013278 (2000)"},{"key":"13_CR24","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1613\/jair.1815","volume":"25","author":"W.J. Pullan","year":"2006","unstructured":"Pullan, W.J., Hoos, H.H.: Dynamic local search for the maximum clique problem. J. Artif. Intell. Res (JAIR)\u00a025, 159\u2013185 (2006)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"13_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1007\/978-3-540-45193-8_43","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"J.-C. R\u00e9gin","year":"2003","unstructured":"R\u00e9gin, J.-C.: Using constraint programming to solve the maximum clique problem. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 634\u2013648. Springer, Heidelberg (2003)"},{"key":"13_CR26","unstructured":"Shen, H., Zhang, H.: Study of lower bounds for Max-2-SAT. In: AAAI (2004)"},{"key":"13_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/3-540-45066-1_22","volume-title":"Discrete Mathematics and Theoretical Computer Science","author":"E. Tomita","year":"2003","unstructured":"Tomita, E., Seki, T.: An efficient branch-and-bound algorithm for finding a maximum clique. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds.) DMTCS 2003. LNCS, vol.\u00a02731, pp. 278\u2013289. Springer, Heidelberg (2003)"},{"key":"13_CR28","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0167-6377(97)00054-0","volume":"21","author":"D. Wood","year":"1997","unstructured":"Wood, D.: An algorithm for finding maximum cliques in a graph. Operations Research Letters\u00a021, 211\u2013217 (1997)","journal-title":"Operations Research Letters"},{"key":"13_CR29","unstructured":"Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: A simple model to generate hard satisfiable instances. In: Proceedings of IJCAI, pp. 337\u2013342 (2005)"},{"key":"13_CR30","unstructured":"Xu, K., Li, W.: Many hard examples in exact phase transitions with application to generating hard satisfiable instances. CoRR, cs.CC\/0302001 (2003)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2008"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79719-7_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:20:08Z","timestamp":1606166408000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79719-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797180","9783540797197"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79719-7_13","relation":{},"subject":[]}}