{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T01:58:01Z","timestamp":1773107881426,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100013000","name":"Politecnico di Torino","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100013000","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The Maximum Common Induced Subgraph problem is a longstanding challenge in graph theory and combinatorial optimization, recognized for being NP-complete and its applications across chemistry, network analysis, and pattern recognition. State-of-the-art methods, such as the McSplit algorithm and its successors, employ a recursive branch-and-bound procedure to navigate the vast solution space. The efficiency of this search is critically dependent on the initial vertex sorting heuristic, which not only guides the algorithm toward a good solution but also structures the search tree for the computationally intensive proof of optimality. The original algorithm relies on a simple node degree heuristic, which is often suboptimal. This paper systematically investigates the influence of alternative vertex-ordering heuristics on McSplitDAL, a state-of-the-art variant of McSplit. We integrate five node-ranking heuristics (namely, PageRank, Betweenness Centrality, Closeness Centrality, Local Clustering Coefficient, and a modified Katz Centrality) into the McSplitDAL framework. We analyze their effect on search-space exploration, pruning efficiency, convergence behavior, and execution speed. We also investigate how they shape the algorithmic search and affect the solver\u2019s ability to approach or prove optimality under constrained computational budgets. Experimental results across heterogeneous datasets reveal that specific heuristics, such as PageRank and Katz Centrality, consistently promote more effective pruning and higher-quality intermediate solutions, offering valuable insights into the relationship between graph topology-derived measures and branch-and-bound performance.<\/jats:p>","DOI":"10.1007\/s10732-025-09575-0","type":"journal-article","created":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T17:24:24Z","timestamp":1764609864000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improving state-of-the-art vertex sorting algorithms to compute the maximum common induced subgraph"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8854-8171","authenticated-orcid":false,"given":"Andrea","family":"Calabrese","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-7553-4839","authenticated-orcid":false,"given":"Lorenzo","family":"Cardone","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-7646-0225","authenticated-orcid":false,"given":"Salvatore","family":"Licata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1428-7818","authenticated-orcid":false,"given":"Marco","family":"Porro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6835-8277","authenticated-orcid":false,"given":"Stefano","family":"Quer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,12,1]]},"reference":[{"key":"9575_CR1","doi-asserted-by":"crossref","unstructured":"Angione, F. et\u00a0al.: An innovative strategy to quickly grade functional test programs. Proceedings of the IEEE International Test Conference (ITC) 355\u2013364 (2022)","DOI":"10.1109\/ITC50671.2022.00044"},{"key":"9575_CR2","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0020-0190(76)90049-1","volume":"4","author":"HG Barrow","year":"1976","unstructured":"Barrow, H.G., Burstall, R.M.: Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques. Inf. Process. Lett. 4, 83\u201384 (1976)","journal-title":"Inf. Process. Lett."},{"key":"9575_CR3","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1121\/1.1906679","volume":"22","author":"A Bavelas","year":"1950","unstructured":"Bavelas, A.: Communication patterns in task-oriented groups. The journal of the acoustical society of America 22, 725\u2013730 (1950)","journal-title":"The journal of the acoustical society of America"},{"key":"9575_CR4","doi-asserted-by":"crossref","unstructured":"Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems. Proceedings of the Seventh International World Wide Web Conference. 30, 107\u2013117 (1998). https:\/\/www.sciencedirect.com\/science\/article\/pii\/S016975529800110X","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"9575_CR5","doi-asserted-by":"publisher","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, 575\u2013576 (1973)","journal-title":"Commun. ACM"},{"key":"9575_CR6","doi-asserted-by":"crossref","unstructured":"Calabrese, A., Cardone, L., Licata, S., Quer, S., Porro, M.: A web scraping algorithm to improve the computation of the maximum common subgraph. Proceedings of the 18$$^{18}$$ International Conference of Software Technologies (ICSOFT 2023) 197\u2013206 (2023)","DOI":"10.5220\/0012130800003538"},{"key":"9575_CR7","doi-asserted-by":"crossref","unstructured":"Cardone, L., Quer, S.: The multi-maximum and quasi-maximum common subgraph problem. MDPI Computation 11 (2023). https:\/\/www.mdpi.com\/2079-3197\/11\/4\/69","DOI":"10.3390\/computation11040069"},{"key":"9575_CR8","doi-asserted-by":"publisher","first-page":"O6","DOI":"10.1186\/1758-2946-5-S1-O6","volume":"5","author":"A Dalke","year":"2013","unstructured":"Dalke, A., Hastings, J.: Fmcs: a novel algorithm for the multiple mcs problem. Journal of cheminformatics 5, O6 (2013)","journal-title":"Journal of cheminformatics"},{"key":"9575_CR9","unstructured":"Foggia, P., Sansone, C., Vento, M.: A database of graphs for isomorphism and sub-graph isomorphism benchmarking. Proc. of the 3rd IAPR TC-15 International Workshop on Graph-based Representations (2001)"},{"key":"9575_CR10","doi-asserted-by":"crossref","unstructured":"Freeman, L.\u00a0C.: A set of measures of centrality based on betweenness. Sociometry 35\u201341 (1977)","DOI":"10.2307\/3033543"},{"key":"9575_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, CA, USA (1979)"},{"key":"9575_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF02289026","volume":"18","author":"L Katz","year":"1953","unstructured":"Katz, L.: A new status index derived from sociometric analysis. Psychometrika 18, 39\u201343 (1953)","journal-title":"Psychometrika"},{"key":"9575_CR13","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection (2014). http:\/\/snap.stanford.edu\/data"},{"key":"9575_CR14","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, 341\u2013352 (1973). https:\/\/doi.org\/10.1007\/BF02575586","journal-title":"Calcolo"},{"key":"9575_CR15","unstructured":"Liu, Y., Zhao, J., Li, C.-M., Jiang, H., He, K.: Hybrid learning with new value function for the maximum common subgraph problem (2022). arXiv:2208.08620"},{"key":"9575_CR16","doi-asserted-by":"crossref","unstructured":"Liu, Y., Li, C.-M., Jiang, H., He, K.: A learning based branch and bound for maximum common subgraph related problems. Proceedings of the AAAI Conference on Artificial Intelligence 34, 2392\u20132399 (2020). https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/5619","DOI":"10.1609\/aaai.v34i03.5619"},{"key":"9575_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-64877-3_2","author":"R Mart\u00ed","year":"2022","unstructured":"Mart\u00ed, R., Reinelt, G.: Heuristic Methods, 27\u201357 (Springer, Berlin Heidelberg, Berlin. Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-662-64877-3_2","journal-title":"Heidelberg"},{"key":"9575_CR18","doi-asserted-by":"crossref","unstructured":"McCreesh, C., Ndiaye, S.\u00a0N., Prosser, P., Solnon, C.: Clique and constraint models for maximum common (connected) subgraph problems. Principles and Practice of Constraint Programming 350\u2013368 (2016)","DOI":"10.1007\/978-3-319-44953-1_23"},{"key":"9575_CR19","doi-asserted-by":"publisher","unstructured":"McCreesh, C., Prosser, P., Trimble, J.: A partitioning algorithm for maximum common subgraph problems. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence IJCAI-17 712\u2013719 (2017). https:\/\/doi.org\/10.24963\/ijcai.2017\/99","DOI":"10.24963\/ijcai.2017\/99"},{"key":"9575_CR20","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"DSJ Michael Garey","year":"1979","unstructured":"Michael Garey, D.S.J.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, United States (1979)"},{"key":"9575_CR21","first-page":"60","volume":"2","author":"S Milgram","year":"1967","unstructured":"Milgram, S.: The small world problem. Psychol. Today 2, 60\u201367 (1967)","journal-title":"Psychol. Today"},{"key":"9575_CR22","doi-asserted-by":"crossref","unstructured":"Park, Y., Reeves, D.: Deriving common malware behavior through graph clustering. Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security 497\u2013502 (2011)","DOI":"10.1145\/1966913.1966986"},{"key":"9575_CR23","doi-asserted-by":"crossref","unstructured":"Quer, S., Marcelli, A., Squillero, G.: The maximum common subgraph problem: A parallel and multi-engine approach. MDPI Computation 8 (2020). https:\/\/www.mdpi.com\/2079-3197\/8\/2\/48","DOI":"10.3390\/computation8020048"},{"key":"9575_CR24","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences 37, 312\u2013323 (1988). https:\/\/www.sciencedirect.com\/science\/article\/pii\/0022000088900104","DOI":"10.1016\/0022-0000(88)90010-4"},{"key":"9575_CR25","unstructured":"Trimble, J.: Partitioning algorithms for induced subgraph problems. Ph.D. thesis, University of Glasgow, Glasgow, UK (2023)"},{"key":"9575_CR26","doi-asserted-by":"crossref","unstructured":"Vismara, P., Valery, B.: Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms. Modelling, Computation and Optimization in Information Systems and Management Sciences: Second International Conference MCO 2008, Metz, France-Luxembourg, September 8-10, 2008. Proceedings 358\u2013368 (2008)","DOI":"10.1007\/978-3-540-87477-5_39"},{"key":"9575_CR27","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393, 440\u2013442 (1998)","journal-title":"Nature"},{"key":"9575_CR28","doi-asserted-by":"crossref","unstructured":"Zhou, J., He, K., Zheng, J., Li, C.-M., Liu, Y.: A strengthened branch and bound algorithm for the maximum common (connected) subgraph problem (2022). arXiv:2201.06252","DOI":"10.24963\/ijcai.2022\/265"},{"key":"9575_CR29","doi-asserted-by":"crossref","unstructured":"Zimmermann, T., Nagappan, N.: Predicting subsystem failures using dependency graph complexities. Proceedings of the 18th IEEE International Symposium on Software Reliability (ISSRE \u201907) 227\u2013236 (2007)","DOI":"10.1109\/ISSRE.2007.19"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-025-09575-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-025-09575-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-025-09575-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T14:21:43Z","timestamp":1773066103000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-025-09575-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["9575"],"URL":"https:\/\/doi.org\/10.1007\/s10732-025-09575-0","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,1]]},"assertion":[{"value":"17 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 November 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no potential conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"1"}}