{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T15:43:50Z","timestamp":1768319030296,"version":"3.49.0"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319232188","type":"print"},{"value":"9783319232195","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23219-5_21","type":"book-chapter","created":{"date-parts":[[2015,8,12]],"date-time":"2015-08-12T10:17:33Z","timestamp":1439374653000},"page":"295-312","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":32,"title":["A Parallel, Backjumping Subgraph Isomorphism Algorithm Using Supplemental Graphs"],"prefix":"10.1007","author":[{"given":"Ciaran","family":"McCreesh","sequence":"first","affiliation":[]},{"given":"Patrick","family":"Prosser","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,13]]},"reference":[{"key":"21_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-319-10428-7_12","volume-title":"Principles and Practice of Constraint Programming","author":"G Audemard","year":"2014","unstructured":"Audemard, G., Lecoutre, C., Samy-Modeliar, M., Goncalves, G., Porumbel, D.: Scoring-based neighborhood dominance for the subgraph isomorphism problem. In: O\u2019Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 125\u2013141. Springer, Heidelberg (2014). http:\/\/dx.doi.org\/10.1007\/978-3-319-10428-7_12"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Bessi\u00e8re, C., R\u00e9gin, J.: MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In: Proceedings of the Second International Conference on Principles and Practice of Constraint Programming, Cambridge, Massachusetts, USA, August 19\u201322, 1996, pp. 61\u201375 (1996). http:\/\/dx.doi.org\/10.1007\/3-540-61551-2_66","DOI":"10.1007\/3-540-61551-2_66"},{"issue":"Suppl 7","key":"21_CR3","doi-asserted-by":"publisher","first-page":"S13","DOI":"10.1186\/1471-2105-14-S7-S13","volume":"14","author":"V Bonnici","year":"2013","unstructured":"Bonnici, V., Giugno, R., Pulvirenti, A., Shasha, D., Ferro, A.: A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinformatics 14(Suppl 7), S13 (2013). http:\/\/www.biomedcentral.com\/1471-2105\/14\/S7\/S13","journal-title":"BMC Bioinformatics"},{"key":"21_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/3-540-60321-2_29","volume-title":"Parallel Algorithms for Irregularly Structured Problems","author":"A de Bruin","year":"1995","unstructured":"de Bruin, A., Kindervater, G.A.P., Trienekens, H.W.J.M.: Asynchronous parallel branch and bound and anomalies. In: Ferreira, A., Rolim, J.D.P. (eds.) IRREGULAR 1995. LNCS, vol. 980, pp. 363\u2013377. Springer, Heidelberg (1995). http:\/\/dx.doi.org\/10.1007\/3-540-60321-2_29"},{"key":"21_CR5","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1613\/jair.788","volume":"14","author":"X Chen","year":"2001","unstructured":"Chen, X., van Beek, P.: Conflict-directed backjumping revisited. J. Artif. Intell. Res. (JAIR) 14, 53\u201381 (2001). http:\/\/dx.doi.org\/10.1613\/jair.788","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"21_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/978-3-642-04244-7_20","volume-title":"Principles and Practice of Constraint Programming - CP 2009","author":"G Chu","year":"2009","unstructured":"Chu, G., Schulte, C., Stuckey, P.J.: Confidence-based work stealing in parallel constraint programming. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 226\u2013241. Springer, Heidelberg (2009). http:\/\/dx.doi.org\/10.1007\/978-3-642-04244-7_20"},{"issue":"3","key":"21_CR7","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/971617.971643","volume":"47","author":"T Coffman","year":"2004","unstructured":"Coffman, T., Greenblatt, S., Marcus, S.: Graph-based technologies for intelligence analysis. Commun. ACM 47(3), 45\u201347 (2004). http:\/\/doi.acm.org\/10.1145\/971617.971643","journal-title":"Commun. ACM"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Conrad, J., Mathew, J.: A backjumping search algorithm for a distributed memory multicomputer. In: International Conference on Parallel Processing, ICPP 1994, vol. 3, pp. 243\u2013246, August 1994","DOI":"10.1109\/ICPP.1994.13"},{"issue":"03","key":"21_CR9","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1142\/S0218001404003228","volume":"18","author":"D Conte","year":"2004","unstructured":"Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence 18(03), 265\u2013298 (2004). http:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218001404003228","journal-title":"International Journal of Pattern Recognition and Artificial Intelligence"},{"key":"21_CR10","unstructured":"Cope, M., Gent, I.P., Hammond, K.: Parallel heuristic search in Haskell. In: Selected Papers from the 2nd Scottish Functional Programming Workshop (SFP00), University of St Andrews, Scotland, July 26\u201328, 2000, pp. 65\u201376 (2000)"},{"issue":"10","key":"21_CR11","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"LP Cordella","year":"2004","unstructured":"Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367\u20131372 (2004). http:\/\/doi.ieeecomputersociety.org\/10.1109\/TPAMI.2004.75","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"7","key":"21_CR12","doi-asserted-by":"publisher","first-page":"996","DOI":"10.1016\/j.cviu.2010.12.013","volume":"115","author":"G Damiand","year":"2011","unstructured":"Damiand, G., Solnon, C., de la Higuera, C., Janodet, J.C., Samuel, \u00c9.: Polynomial algorithms for subisomorphism of $$n$$D open combinatorial maps. Computer Vision and Image Understanding 115(7), 996\u20131010 (2011). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S1077314211000816, special issue on Graph-Based Representations in Computer Vision","journal-title":"Computer Vision and Image Understanding"},{"key":"21_CR13","unstructured":"Geelen, P.A.: Dual viewpoint heuristics for binary constraint satisfaction problems. In: ECAI, pp. 31\u201335 (1992)"},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-642-11503-5_19","volume-title":"Practical Aspects of Declarative Languages","author":"IP Gent","year":"2010","unstructured":"Gent, I.P., Miguel, I., Moore, N.C.A.: Lazy explanations for constraint propagators. In: Carro, M., Pe\u00f1a, R. (eds.) PADL 2010. LNCS, vol. 5937, pp. 217\u2013233. Springer, Heidelberg (2010). http:\/\/dx.doi.org\/10.1007\/978-3-642-11503-5_19"},{"issue":"18","key":"21_CR15","doi-asserted-by":"publisher","first-page":"1973","DOI":"10.1016\/j.artint.2008.10.006","volume":"172","author":"IP Gent","year":"2008","unstructured":"Gent, I.P., Miguel, I., Nightingale, P.: Generalised arc consistency for the alldifferent constraint: An empirical survey. Artificial Intelligence 172(18), 1973\u20132000 (2008). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0004370208001410, special Review Issue","journal-title":"Artificial Intelligence"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Giugno, R., Bonnici, V., Bombieri, N., Pulvirenti, A., Ferro, A., Shasha, D.: Grapes: A software for parallel searching on biological graphs targeting multi-core architectures. PLoS ONE 8(10), e76911 (2013) http:\/\/dx.doi.org\/10.1371%2Fjournal.pone.0076911","DOI":"10.1371\/journal.pone.0076911"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Habbas, Z., Herrmann, F., Merel, P.P., Singer, D.: Load balancing strategies for parallel forward search algorithm with conflict based backjumping. In: Proceedings of the 1997 International Conference on Parallel and Distributed Systems, pp. 376\u2013381, December 1997","DOI":"10.1109\/ICPADS.1997.652576"},{"key":"21_CR18","unstructured":"Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. In: IJCAI (1), pp. 607\u2013615. Morgan Kaufmann, San Francisco (1995)"},{"key":"21_CR19","unstructured":"Kessel, P.V., Quimper, C.: Filtering algorithms based on the word-RAM model. In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22\u201326, 2012, Toronto, Ontario, Canada. (2012). http:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI12\/paper\/view\/5135"},{"issue":"4","key":"21_CR20","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1017\/S0960129501003577","volume":"12","author":"J Larrosa","year":"2002","unstructured":"Larrosa, J., Valiente, G.: Constraint satisfaction algorithms for graph pattern matching. Mathematical Structures in Computer Science 12(4), 403\u2013422 (2002). http:\/\/dx.doi.org\/10.1017\/S0960129501003577","journal-title":"Mathematical Structures in Computer Science"},{"key":"21_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-642-29822-6_17","volume-title":"Functional and Logic Programming","author":"O Lobachev","year":"2012","unstructured":"Lobachev, O.: Parallel computation skeletons with premature termination property. In: Schrijvers, T., Thiemann, P. (eds.) FLOPS 2012. LNCS, vol. 7294, pp. 197\u2013212. Springer, Heidelberg (2012). http:\/\/dx.doi.org\/10.1007\/978-3-642-29822-6_17"},{"key":"21_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/3-540-49481-2_24","volume-title":"Principles and Practice of Constraint Programming - CP98","author":"E MacIntyre","year":"1998","unstructured":"MacIntyre, E., Prosser, P., Smith, B.M., Walsh, T.: Random constraint satisfaction: theory meets practice. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, p. 325. Springer, Heidelberg (1998). http:\/\/dx.doi.org\/10.1007\/3-540-49481-2_24"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Malitsky, Y.: Instance-Specific Algorithm Configuration. Springer (2014). http:\/\/dx.doi.org\/10.1007\/978-3-319-11230-5","DOI":"10.1007\/978-3-319-11230-5"},{"issue":"1","key":"21_CR24","doi-asserted-by":"publisher","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). http:\/\/doi.acm.org\/10.1145\/2742359","journal-title":"ACM Trans. Parallel Comput."},{"issue":"3","key":"21_CR25","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0255(79)90023-9","volume":"19","author":"JJ McGregor","year":"1979","unstructured":"McGregor, J.J.: Relational consistency algorithms and their application in finding subgraph and graph isomorphisms. Inf. Sci. 19(3), 229\u2013250 (1979). http:\/\/dx.doi.org\/10.1016\/0020-0255(79)90023\u20139","journal-title":"Inf. Sci."},{"key":"21_CR26","unstructured":"Prosser, P.: Domain filtering can degrade intelligent backtracking search. In: Proceedings of the 13th International Joint Conference on Artifical Intelligence, IJCAI 1993 ,vol. 1, pp. 262\u2013267. Morgan Kaufmann Publishers Inc., San Francisco (1993). http:\/\/dl.acm.org\/citation.cfm?id=1624025.1624062"},{"key":"21_CR27","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1111\/j.1467-8640.1993.tb00310.x","volume":"9","author":"P Prosser","year":"1993","unstructured":"Prosser, P.: Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence 9, 268\u2013299 (1993). http:\/\/dx.doi.org\/10.1111\/j.1467-8640.1993.tb00310.x","journal-title":"Computational Intelligence"},{"key":"21_CR28","unstructured":"Puget, J.: A fast algorithm for the bound consistency of alldiff constraints. In: Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference, AAAI 1998, IAAI 1998, July 26\u201330, 1998, Madison, Wisconsin, USA, pp. 359\u2013366 (1998). http:\/\/www.aaai.org\/Library\/AAAI\/1998\/aaai98-051.php"},{"key":"21_CR29","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11754602_1","volume-title":"Recent Advances in Constraints","author":"C-G Quimper","year":"2006","unstructured":"Quimper, C.-G., Walsh, T.: The all different and global cardinality constraints on set, multiset and tuple variables. In: Hnich, B., Carlsson, M., Fages, F., Rossi, F. (eds.) CSCLP 2005. LNCS (LNAI), vol. 3978, pp. 1\u201313. Springer, Heidelberg (2006). http:\/\/dx.doi.org\/10.1007\/11754602_1"},{"key":"21_CR30","unstructured":"R\u00e9gin, J.: A filtering algorithm for constraints of difference in CSPs. In: Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31\u2013 August 4, 1994, vol. 1, pp. 362\u2013367 (1994). http:\/\/www.aaai.org\/Library\/AAAI\/1994\/aaai94-055.php"},{"key":"21_CR31","unstructured":"R\u00e9gin, J.C.: D\u00e9veloppement d\u2019outils algorithmiques pour l\u2019Intelligence Artificielle. Application \u00e0 la chimie organique. Ph.D. thesis, Universit\u00e9 Montpellier 2 (1995)"},{"key":"21_CR32","doi-asserted-by":"crossref","unstructured":"San Segundo, P., Rodriguez-Losada, D., Galan, R., Matia, F., Jimenez, A.: Exploiting CPU bit parallel operations to improve efficiency in search. In: 19th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2007, vol. 1, pp. 53\u201359, October 2007","DOI":"10.1109\/ICTAI.2007.40"},{"key":"21_CR33","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.tcs.2015.02.011","volume":"577","author":"M Sevegnani","year":"2015","unstructured":"Sevegnani, M., Calder, M.: Bigraphs with sharing. Theoretical Computer Science 577, 43\u201373 (2015). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397515001085","journal-title":"Theoretical Computer Science"},{"key":"21_CR34","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1017\/nws.2014.22","volume":"2","author":"N Slater","year":"2014","unstructured":"Slater, N., Itzchack, R., Louzoun, Y.: Mid size cliques are more common in real world networks than triangles. Network Science 2, 387\u2013402 (2014). http:\/\/journals.cambridge.org\/article_S2050124214000228","journal-title":"Network Science"},{"key":"21_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/BFb0017439","volume-title":"Principles and Practice of Constraint Programming - CP97","author":"BM Smith","year":"1997","unstructured":"Smith, B.M., Grant, S.A.: Modelling exceptionally hard constraint satisfaction problems. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 182\u2013195. Springer, Heidelberg (1997). http:\/\/dx.doi.org\/10.1007\/BFb0017439"},{"issue":"12\u201313","key":"21_CR36","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1016\/j.artint.2010.05.002","volume":"174","author":"C Solnon","year":"2010","unstructured":"Solnon, C.: Alldifferent-based filtering for subgraph isomorphism. Artif. Intell. 174(12\u201313), 850\u2013864 (2010). http:\/\/dx.doi.org\/10.1016\/j.artint.2010.05.002","journal-title":"Artif. Intell."},{"issue":"2","key":"21_CR37","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/j.patcog.2014.05.019","volume":"48","author":"C Solnon","year":"2015","unstructured":"Solnon, C., Damiand, G., de la Higuera, C., Janodet, J.C.: On the complexity of submap isomorphism and maximum common submap problems. Pattern Recognition 48(2), 302\u2013316 (2015). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0031320314002192","journal-title":"Pattern Recognition"},{"key":"21_CR38","unstructured":"Trienekens, H.W.: Parallel Branch and Bound Algorithms. Ph.D. thesis, Erasmus University Rotterdam (1990)"},{"issue":"1","key":"21_CR39","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"JR Ullmann","year":"1976","unstructured":"Ullmann, J.R.: An algorithm for subgraph isomorphism. Journal of the ACM (JACM) 23(1), 31\u201342 (1976)","journal-title":"Journal of the ACM (JACM)"},{"key":"21_CR40","first-page":"1.6:1.1","volume":"15","author":"JR Ullmann","year":"2011","unstructured":"Ullmann, J.R.: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. J. Exp. Algorithmics 15, 1.6:1.1\u20131.6:1.64 (2011). http:\/\/doi.acm.org\/10.1145\/1671970.1921702","journal-title":"J. Exp. Algorithmics"},{"issue":"3","key":"21_CR41","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s10601-009-9074-3","volume":"15","author":"S Zampelli","year":"2010","unstructured":"Zampelli, S., Deville, Y., Solnon, C.: Solving subgraph isomorphism problems with constraint programming. Constraints 15(3), 327\u2013353 (2010). http:\/\/dx.doi.org\/10.1007\/s10601-009-9074-3","journal-title":"Constraints"}],"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-319-23219-5_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T23:47:41Z","timestamp":1748562461000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23219-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319232188","9783319232195"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23219-5_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"13 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}