{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:56:58Z","timestamp":1764403018606,"version":"3.40.3"},"publisher-location":"Cham","reference-count":74,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030584740"},{"type":"electronic","value":"9783030584757"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-58475-7_20","type":"book-chapter","created":{"date-parts":[[2020,9,6]],"date-time":"2020-09-06T20:02:35Z","timestamp":1599422555000},"page":"338-357","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5459-3134","authenticated-orcid":false,"given":"Stephan","family":"Gocht","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0032-9506","authenticated-orcid":false,"given":"Ross","family":"McBride","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6106-4871","authenticated-orcid":false,"given":"Ciaran","family":"McCreesh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2700-4285","authenticated-orcid":false,"given":"Jakob","family":"Nordstr\u00f6m","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4460-6912","authenticated-orcid":false,"given":"Patrick","family":"Prosser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7282-8745","authenticated-orcid":false,"given":"James","family":"Trimble","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,2]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Atserias, A., Bonacina, I., de Rezende, S.F., Lauria, M., Nordstr\u00f6m, J., Razborov, A.A.: Clique is hard on average for regular resolution. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, 25\u201329 June 2018, pp. 866\u2013877 (2018)","DOI":"10.1145\/3188745.3188856"},{"issue":"1","key":"20_CR2","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/BF02243394","volume":"52","author":"L Babel","year":"1994","unstructured":"Babel, L.: A fast algorithm for the maximum weight clique problem. Computing 52(1), 31\u201338 (1994)","journal-title":"Computing"},{"issue":"4","key":"20_CR3","doi-asserted-by":"crossref","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 J. Comput. 15(4), 1054\u20131068 (1986)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"20_CR4","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/s10878-012-9592-6","volume":"27","author":"M Batsyn","year":"2014","unstructured":"Batsyn, M., Goldengorin, B., Maslov, E., Pardalos, P.M.: Improvements to MCS algorithm for the maximum clique problem. J. Comb. Optim. 27(2), 397\u2013416 (2014)","journal-title":"J. Comb. Optim."},{"key":"20_CR5","unstructured":"Biere, A.: Tracecheck (2006). http:\/\/fmv.jku.at\/tracecheck\/"},{"issue":"9","key":"20_CR6","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Finding all cliques of an undirected graph (algorithm 457). Commun. ACM 16(9), 575\u2013576 (1973)","journal-title":"Commun. ACM"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-642-14186-7_6","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2010","author":"R Brummayer","year":"2010","unstructured":"Brummayer, R., Lonsing, F., Biere, A.: Automated testing and debugging of SAT and QBF solvers. In: Strichman, O., Szeider, S. (eds.) SAT 2010. LNCS, vol. 6175, pp. 44\u201357. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14186-7_6"},{"key":"20_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/3-540-61551-2_68","volume-title":"Principles and Practice of Constraint Programming \u2014 CP96","author":"BMW Cheng","year":"1996","unstructured":"Cheng, B.M.W., Lee, J.H.M., Wu, J.C.K.: Speeding up constraint propagation by redundant modeling. In: Freuder, E.C. (ed.) CP 1996. LNCS, vol. 1118, pp. 91\u2013103. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61551-2_68"},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/11941439_9","volume-title":"AI 2006: Advances in Artificial Intelligence","author":"CW Choi","year":"2006","unstructured":"Choi, C.W., Harvey, W., Lee, J.H.M., Stuckey, P.J.: Finite domain bounds consistency revisited. In: Sattar, A., Kang, B. (eds.) AI 2006. LNCS (LNAI), vol. 4304, pp. 49\u201358. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11941439_9"},{"issue":"1","key":"20_CR10","doi-asserted-by":"crossref","first-page":"99","DOI":"10.7155\/jgaa.00139","volume":"11","author":"D Conte","year":"2007","unstructured":"Conte, D., Foggia, P., Vento, M.: Challenging complexity of maximum common subgraph detection algorithms: a performance analysis of three algorithms on a wide database of graphs. J. Graph Algorithms Appl. 11(1), 99\u2013143 (2007)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"20_CR11","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(87)90039-4","volume":"18","author":"WJ Cook","year":"1987","unstructured":"Cook, W.J., Coullard, C.R., Tur\u00e1n, G.: On the complexity of cutting-plane proofs. Discret. Appl. Math. 18(1), 25\u201338 (1987)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"20_CR12","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/s12532-013-0055-6","volume":"5","author":"WJ Cook","year":"2013","unstructured":"Cook, W.J., Koch, T., Steffy, D.E., Wolter, K.: A hybrid branch-and-bound approach for exact rational mixed-integer programming. Math. Program. Comput. 5(3), 305\u2013344 (2013)","journal-title":"Math. Program. Comput."},{"key":"20_CR13","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/978-3-319-63046-5_14","volume-title":"Automated Deduction \u2013 CADE 26","author":"L Cruz-Filipe","year":"2017","unstructured":"Cruz-Filipe, L., Heule, M.J.H., Hunt, W.A., Kaufmann, M., Schneider-Kamp, P.: Efficient certified RAT verification. In: de Moura, L. (ed.) CADE 2017. LNCS (LNAI), vol. 10395, pp. 220\u2013236. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63046-5_14"},{"key":"20_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-662-54577-5_7","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"L Cruz-Filipe","year":"2017","unstructured":"Cruz-Filipe, L., Marques-Silva, J., Schneider-Kamp, P.: Efficient certified resolution proof checking. In: Legay, A., Margaria, T. (eds.) TACAS 2017. LNCS, vol. 10205, pp. 118\u2013135. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-54577-5_7"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Dasari, N.S., Ranjan, D., Zubair, M.: pbitMCE: a bit-based approach for maximal clique enumeration on multicore processors. In: 20th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2014, Hsinchu, Taiwan, 16\u201319 December 2014, pp. 478\u2013485 (2014)","DOI":"10.1109\/PADSW.2014.7097844"},{"issue":"9","key":"20_CR16","doi-asserted-by":"crossref","first-page":"2217","DOI":"10.1021\/ci4002525","volume":"53","author":"M Depolli","year":"2013","unstructured":"Depolli, M., Konc, J., Rozman, K., Trobec, R., Janezic, D.: Exact parallel maximum clique algorithm for general and protein graphs. J. Chem. Inf. Model. 53(9), 2217\u20132228 (2013)","journal-title":"J. Chem. Inf. Model."},{"issue":"17","key":"20_CR17","first-page":"1","volume":"2","author":"PJ Durand","year":"1999","unstructured":"Durand, P.J., Pasari, R., Baker, J.W., Tsai, C.C.: An efficient algorithm for similarity analysis of molecules. Internet J. Chem. 2(17), 1\u201316 (1999)","journal-title":"Internet J. Chem."},{"issue":"1","key":"20_CR18","first-page":"68","volume":"1","author":"HC Ehrlich","year":"2011","unstructured":"Ehrlich, H.C., Rarey, M.: Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review. Wiley Interdiscip. Rev.: Comput. Mol. Sci. 1(1), 68\u201379 (2011)","journal-title":"Wiley Interdiscip. Rev.: Comput. Mol. Sci."},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Elffers, J., Gocht, S., McCreesh, C., Nordstr\u00f6m, J.: Justifying all differences using pseudo-boolean reasoning. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, 7\u201312 February 2020, pp. 1486\u20131494 (2020)","DOI":"10.1609\/aaai.v34i02.5507"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. ACM J. Exp. Algorithmics 18 (2013)","DOI":"10.1145\/2543629"},{"key":"20_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-20662-7_31","volume-title":"Experimental Algorithms","author":"D Eppstein","year":"2011","unstructured":"Eppstein, D., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 364\u2013375. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20662-7_31"},{"key":"20_CR22","unstructured":"Gange, G., Stuckey, P.J.: Certifying optimality in constraint programming, February 2019. Presentation at KTH Royal Institute of Technology. Slides https:\/\/www.kth.se\/polopoly_fs\/1.879851.1550484700!\/CertifiedCP.pdf"},{"key":"20_CR23","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/j.dam.2013.08.008","volume":"162","author":"S Gay","year":"2014","unstructured":"Gay, S., Fages, F., Martinez, T., Soliman, S., Solnon, C.: On the subgraph epimorphism problem. Discret. Appl. Math. 162, 214\u2013228 (2014)","journal-title":"Discret. Appl. Math."},{"key":"20_CR24","unstructured":"Gelder, A.V.: Verifying RUP proofs of propositional unsatisfiability. In: International Symposium on Artificial Intelligence and Mathematics, ISAIM 2008, Fort Lauderdale, Florida, USA, 2\u20134 January 2008 (2008)"},{"key":"20_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/978-3-030-30048-7_33","volume-title":"Principles and Practice of Constraint Programming","author":"X Gillard","year":"2019","unstructured":"Gillard, X., Schaus, P., Deville, Y.: SolverCheck: declarative testing of constraints. In: Schiex, T., de Givry, S. (eds.) CP 2019. LNCS, vol. 11802, pp. 565\u2013582. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-30048-7_33"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Gocht, S., McCreesh, C., Nordstr\u00f6m, J.: Subgraph isomorphism meets cutting planes: solving with certified solutions. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020 [scheduled for July 2020, Yokohama, Japan, postponed due to the Corona pandemic], pp. 1134\u20131140 (2020)","DOI":"10.24963\/ijcai.2020\/158"},{"key":"20_CR27","unstructured":"Goldberg, E.I., Novikov, Y.: Verification of proofs of unsatisfiability for CNF formulas. In: 2003 Design, Automation and Test in Europe Conference and Exposition (DATE 2003), Munich, Germany, 3\u20137 March 2003, pp. 10886\u201310891. IEEE Computer Society (2003)"},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"Hespe, D., Lamm, S., Schulz, C., Strash, D.: WeGotYouCovered: the winning solver from the PACE 2019 implementation challenge, vertex cover track. CoRR abs\/1908.06795 (2019)","DOI":"10.1137\/1.9781611976229.1"},{"key":"20_CR29","doi-asserted-by":"crossref","unstructured":"Heule, M., Hunt Jr., W.A., Wetzler, N.: Trimming while checking clausal proofs. In: Formal Methods in Computer-Aided Design, FMCAD 2013, Portland, OR, USA, 20\u201323 October 2013, pp. 181\u2013188 (2013)","DOI":"10.1109\/FMCAD.2013.6679408"},{"key":"20_CR30","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-642-38574-2_24","volume-title":"Automated Deduction \u2013 CADE-24","author":"MJH Heule","year":"2013","unstructured":"Heule, M.J.H., Hunt, W.A., Wetzler, N.: Verifying refutations with extended resolution. In: Bonacina, M.P. (ed.) CADE 2013. LNCS (LNAI), vol. 7898, pp. 345\u2013359. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38574-2_24"},{"key":"20_CR31","unstructured":"Hoffmann, R., McCreesh, C., Reilly, C.: Between subgraph isomorphism and maximum common subgraph. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, California, USA, 4\u20139 February 2017, pp. 3907\u20133914 (2017)"},{"key":"20_CR32","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., Trick, M.A.: Introduction to the second DIMACS challenge: cliques, coloring, and satisfiability. In: Cliques, Coloring, and Satisfiability, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, 11\u201313 October 1993, pp. 1\u201310 (1993)","DOI":"10.1090\/dimacs\/026\/01"},{"issue":"3","key":"20_CR33","first-page":"569","volume":"58","author":"J Konc","year":"2007","unstructured":"Konc, J., Jane\u017ei\u010d, D.: An improved branch and bound algorithm for the maximum clique problem. MATCH Commun. Math. Comput. Chem. 58(3), 569\u2013590 (2007)","journal-title":"MATCH Commun. Math. Comput. Chem."},{"issue":"4","key":"20_CR34","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/BF02575586","volume":"9","author":"G Levi","year":"1973","unstructured":"Levi, G.: A note on the derivation of maximal common subgraphs of two directed or undirected graphs. CALCOLO 9(4), 341\u2013352 (1973). https:\/\/doi.org\/10.1007\/BF02575586","journal-title":"CALCOLO"},{"key":"20_CR35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cor.2017.02.017","volume":"84","author":"C Li","year":"2017","unstructured":"Li, C., Jiang, H., Many\u00e0, F.: On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem. Comput. Oper. Res. 84, 1\u201315 (2017)","journal-title":"Comput. Oper. Res."},{"key":"20_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/978-3-319-19084-6_26","volume-title":"Learning and Intelligent Optimization","author":"C-M Li","year":"2015","unstructured":"Li, C.-M., Jiang, H., Xu, R.-C.: Incremental MaxSAT reasoning to reduce branches in a branch-and-bound algorithm for MaxClique. In: Dhaenens, C., Jourdan, L., Marmion, M.-E. (eds.) LION 2015. LNCS, vol. 8994, pp. 268\u2013274. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-19084-6_26"},{"key":"20_CR37","unstructured":"Li, C.M., Quan, Z.: An efficient branch-and-bound algorithm based on MaxSAT for the maximum clique problem. In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, 11\u201315 July 2010 (2010)"},{"key":"20_CR38","doi-asserted-by":"crossref","unstructured":"Liu, Y., Li, C., Jiang, H., He, K.: A learning based branch and bound for maximum common subgraph related problems. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, 7\u201312 February 2020, pp. 2392\u20132399 (2020)","DOI":"10.1609\/aaai.v34i03.5619"},{"issue":"1","key":"20_CR39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10898-013-0075-9","volume":"59","author":"E Maslov","year":"2014","unstructured":"Maslov, E., Batsyn, M., Pardalos, P.M.: Speeding up branch and bound algorithms for solving the maximum clique problem. J. Glob. Optim. 59(1), 1\u201321 (2014)","journal-title":"J. Glob. Optim."},{"issue":"2","key":"20_CR40","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.cosrev.2010.09.009","volume":"5","author":"RM McConnell","year":"2011","unstructured":"McConnell, R.M., Mehlhorn, K., N\u00e4her, S., Schweitzer, P.: Certifying algorithms. Comput. Sci. Rev. 5(2), 119\u2013161 (2011)","journal-title":"Comput. Sci. Rev."},{"key":"20_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/978-3-319-44953-1_23","volume-title":"Principles and Practice of Constraint Programming","author":"C McCreesh","year":"2016","unstructured":"McCreesh, C., Ndiaye, S.N., Prosser, P., Solnon, C.: Clique and constraint models for maximum common (connected) subgraph problems. In: Rueher, M. (ed.) CP 2016. LNCS, vol. 9892, pp. 350\u2013368. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-44953-1_23"},{"key":"20_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-030-30048-7_20","volume-title":"Principles and Practice of Constraint Programming","author":"C McCreesh","year":"2019","unstructured":"McCreesh, C., Pettersson, W., Prosser, P.: Understanding the empirical hardness of random optimisation problems. In: Schiex, T., de Givry, S. (eds.) CP 2019. LNCS, vol. 11802, pp. 333\u2013349. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-30048-7_20"},{"issue":"4","key":"20_CR43","doi-asserted-by":"crossref","first-page":"618","DOI":"10.3390\/a6040618","volume":"6","author":"C McCreesh","year":"2013","unstructured":"McCreesh, C., Prosser, P.: Multi-threading a state-of-the-art maximum clique algorithm. Algorithms 6(4), 618\u2013635 (2013)","journal-title":"Algorithms"},{"key":"20_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/978-3-319-10428-7_40","volume-title":"Principles and Practice of Constraint Programming","author":"C McCreesh","year":"2014","unstructured":"McCreesh, C., Prosser, P.: Reducing the branching in a branch and bound algorithm for the maximum clique problem. In: O\u2019Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 549\u2013563. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-10428-7_40"},{"issue":"1","key":"20_CR45","doi-asserted-by":"crossref","first-page":"8:1","DOI":"10.1145\/2742359","volume":"2","author":"C McCreesh","year":"2015","unstructured":"McCreesh, C., Prosser, P.: The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound. ACM Trans. Parallel Comput. 2(1), 8:1\u20138:27 (2015)","journal-title":"ACM Trans. Parallel Comput."},{"key":"20_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-319-66158-2_14","volume-title":"Principles and Practice of Constraint Programming","author":"C McCreesh","year":"2017","unstructured":"McCreesh, C., Prosser, P., Simpson, K., Trimble, J.: On maximum weight clique algorithms, and how they are evaluated. In: Beck, J.C. (ed.) CP 2017. LNCS, vol. 10416, pp. 206\u2013225. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-66158-2_14"},{"key":"20_CR47","doi-asserted-by":"crossref","unstructured":"McCreesh, C., Prosser, P., Trimble, J.: A partitioning algorithm for maximum common subgraph problems. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, 19\u201325 August 2017, pp. 712\u2013719 (2017)","DOI":"10.24963\/ijcai.2017\/99"},{"key":"20_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/978-3-030-51372-6_19","volume-title":"Graph Transformation","author":"C McCreesh","year":"2020","unstructured":"McCreesh, C., Prosser, P., Trimble, J.: The Glasgow subgraph solver: using constraint programming to tackle hard subgraph isomorphism problem variants. In: Gadducci, F., Kehrer, T. (eds.) ICGT 2020. LNCS, vol. 12150, pp. 316\u2013324. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-51372-6_19"},{"key":"20_CR49","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.tcs.2015.11.016","volume":"613","author":"KA Naud\u00e9","year":"2016","unstructured":"Naud\u00e9, K.A.: Refined pivot selection for maximal clique enumeration in graphs. Theor. Comput. Sci. 613, 28\u201337 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/978-3-642-23786-7_48","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2011","author":"SN Ndiaye","year":"2011","unstructured":"Ndiaye, S.N., Solnon, C.: CP models for maximum common subgraph problems. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 637\u2013644. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23786-7_48"},{"key":"20_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-319-19084-6_27","volume-title":"Learning and Intelligent Optimization","author":"A Nikolaev","year":"2015","unstructured":"Nikolaev, A., Batsyn, M., Segundo, P.S.: Reusing the same coloring in the child nodes of the search tree for the maximum clique problem. In: Dhaenens, C., Jourdan, L., Marmion, M.-E. (eds.) LION 2015. LNCS, vol. 8994, pp. 275\u2013280. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-19084-6_27"},{"key":"20_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/3-540-45578-7_31","volume-title":"Principles and Practice of Constraint Programming \u2014 CP 2001","author":"T Petit","year":"2001","unstructured":"Petit, T., R\u00e9gin, J.-C., Bessi\u00e8re, C.: Specific filtering algorithms for over-constrained problems. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 451\u2013463. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45578-7_31"},{"issue":"4","key":"20_CR53","doi-asserted-by":"crossref","first-page":"545","DOI":"10.3390\/a5040545","volume":"5","author":"P Prosser","year":"2012","unstructured":"Prosser, P.: Exact algorithms for maximum clique: a computational study. Algorithms 5(4), 545\u2013587 (2012)","journal-title":"Algorithms"},{"issue":"7","key":"20_CR54","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1023\/A:1021271615909","volume":"16","author":"JW Raymond","year":"2002","unstructured":"Raymond, J.W., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J. Comput. Aided Mol. Des. 16(7), 521\u2013533 (2002)","journal-title":"J. Comput. Aided Mol. Des."},{"key":"20_CR55","unstructured":"Roussel, O., Manquinho, V.M.: Input\/output format and solver requirements for the competitions of pseudo-Boolean solvers, January 2016. Revision 2324. http:\/\/www.cril.univ-artois.fr\/PB16\/format.pdf"},{"key":"20_CR56","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.cor.2019.05.017","volume":"110","author":"P San Segundo","year":"2019","unstructured":"San Segundo, P., Furini, F., Artieda, J.: A new branch-and-bound algorithm for the maximum weighted clique problem. Comput. Oper. Res. 110, 18\u201333 (2019)","journal-title":"Comput. Oper. Res."},{"key":"20_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-319-09584-4_12","volume-title":"Learning and Intelligent Optimization","author":"P San Segundo","year":"2014","unstructured":"San Segundo, P., Lopez, A., Batsyn, M.: Initial sorting of vertices in the maximum clique problem reviewed. In: Pardalos, P.M., Resende, M.G.C., Vogiatzis, C., Walteros, J.L. (eds.) LION 2014. LNCS, vol. 8426, pp. 111\u2013120. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-09584-4_12"},{"issue":"3","key":"20_CR58","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1007\/s10489-016-0796-9","volume":"45","author":"P San Segundo","year":"2016","unstructured":"San Segundo, P., Lopez, A., Batsyn, M., Nikolaev, A., Pardalos, P.M.: Improved initial vertex ordering for exact maximum clique search. Appl. Intell. 45(3), 868\u2013880 (2016)","journal-title":"Appl. Intell."},{"issue":"3","key":"20_CR59","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/s11590-011-0431-y","volume":"7","author":"P San Segundo","year":"2013","unstructured":"San Segundo, P., Mat\u00eda, F., Rodr\u00edguez-Losada, D., Hernando, M.: An improved bit parallel exact maximum clique algorithm. Optim. Lett. 7(3), 467\u2013479 (2013)","journal-title":"Optim. Lett."},{"key":"20_CR60","unstructured":"San Segundo, P., Nikolaev, A., Batsyn, M., Pardalos, P.M.: Improved infra-chromatic bound for exact maximum clique search. Informatica Lith. Acad. Sci. 27(2), 463\u2013487 (2016)"},{"issue":"2","key":"20_CR61","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/j.cor.2010.07.019","volume":"38","author":"P San Segundo","year":"2011","unstructured":"San Segundo, P., Rodr\u00edguez-Losada, D., Jim\u00e9nez, A.: An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Res. 38(2), 571\u2013581 (2011)","journal-title":"Comput. Oper. Res."},{"key":"20_CR62","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.cor.2013.10.018","volume":"44","author":"P San Segundo","year":"2014","unstructured":"San Segundo, P., Tapia, C.: Relaxed approximate coloring in exact maximum clique search. Comput. Oper. Res. 44, 185\u2013192 (2014)","journal-title":"Comput. Oper. Res."},{"issue":"8","key":"20_CR63","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1016\/S0167-8655(02)00253-2","volume":"24","author":"MD Santo","year":"2003","unstructured":"Santo, M.D., Foggia, P., Sansone, C., Vento, M.: A large database of graphs and its use for benchmarking graph isomorphism algorithms. Pattern Recogn. Lett. 24(8), 1067\u20131079 (2003)","journal-title":"Pattern Recogn. Lett."},{"key":"20_CR64","unstructured":"Tavares, A.W.: Algoritmos exatos para problema da clique maxima ponderada. Ph.D. thesis, Universidade federal do Cear\u00e1 (2016)"},{"key":"20_CR65","unstructured":"Tavares, W.A., Neto, M.B.C., Rodrigues, C.D., Michelon, P.: Um algoritmo de branch and bound para o problema da clique m\u00e1xima ponderada. In: Proceedings of XLVII SBPO, vol. 1 (2015)"},{"issue":"1","key":"20_CR66","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s10898-006-9039-7","volume":"37","author":"E Tomita","year":"2007","unstructured":"Tomita, E., Kameda, T.: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Glob. Optim. 37(1), 95\u2013111 (2007)","journal-title":"J. Glob. Optim."},{"key":"20_CR67","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. 2731, pp. 278\u2013289. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45066-1_22"},{"key":"20_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-642-11440-3_18","volume-title":"WALCOM: Algorithms and Computation","author":"E Tomita","year":"2010","unstructured":"Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., Wakatsuki, M.: A simple and faster branch-and-bound algorithm for finding a maximum clique. In: Rahman, M.S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol. 5942, pp. 191\u2013203. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11440-3_18"},{"key":"20_CR69","doi-asserted-by":"crossref","unstructured":"Tomita, E., Sutani, Y., Higashi, T., Wakatsuki, M.: A simple and faster branch-and-bound algorithm for finding a maximum clique with computational experiments. IEICE Trans. Inf. Syst. 96-D(6), 1286\u20131298 (2013)","DOI":"10.1587\/transinf.E96.D.1286"},{"issue":"1","key":"20_CR70","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.tcs.2006.06.015","volume":"363","author":"E Tomita","year":"2006","unstructured":"Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci. 363(1), 28\u201342 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR71","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-3-319-39817-4_21","volume-title":"Frontiers in Algorithmics","author":"E Tomita","year":"2016","unstructured":"Tomita, E., Yoshida, K., Hatta, T., Nagao, A., Ito, H., Wakatsuki, M.: A much faster branch-and-bound algorithm for finding a maximum clique. In: Zhu, D., Bereg, S. (eds.) FAW 2016. LNCS, vol. 9711, pp. 215\u2013226. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-39817-4_21"},{"key":"20_CR72","unstructured":"Veksler, M., Strichman, O.: A proof-producing CSP solver. In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, 11\u201315 July 2010 (2010)"},{"key":"20_CR73","series-title":"Communications in Computer and Information Science","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/978-3-540-87477-5_39","volume-title":"Modelling, Computation and Optimization in Information Systems and Management Sciences","author":"P Vismara","year":"2008","unstructured":"Vismara, P., Valery, B.: Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms. In: Le Thi, H.A., Bouvry, P., Pham Dinh, T. (eds.) MCO 2008. CCIS, vol. 14, pp. 358\u2013368. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87477-5_39"},{"key":"20_CR74","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/978-3-319-09284-3_31","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2014","author":"N Wetzler","year":"2014","unstructured":"Wetzler, N., Heule, M.J.H., Hunt, W.A.: DRAT-trim: efficient checking and trimming using expressive clausal proofs. In: Sinz, C., Egly, U. (eds.) SAT 2014. LNCS, vol. 8561, pp. 422\u2013429. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-09284-3_31"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-58475-7_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,24]],"date-time":"2021-04-24T05:35:23Z","timestamp":1619242523000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-58475-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030584740","9783030584757"],"references-count":74,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-58475-7_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"2 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Principles and Practice of Constraint Programming","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Louvain-la-Neuve","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Belgium","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cp2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cp2020.a4cp.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"122","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"55","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"45% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.13","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.47","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}