{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:50:17Z","timestamp":1764175817787,"version":"3.44.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T00:00:00Z","timestamp":1750636800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T00:00:00Z","timestamp":1750636800000},"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":["Combinatorica"],"published-print":{"date-parts":[[2025,8]]},"DOI":"10.1007\/s00493-025-00157-z","type":"journal-article","created":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T03:56:59Z","timestamp":1750651019000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Isomorphisms Between Dense Random Graphs"],"prefix":"10.1007","volume":"45","author":[{"given":"Erlang","family":"Surya","sequence":"first","affiliation":[]},{"given":"Lutz","family":"Warnke","sequence":"additional","affiliation":[]},{"given":"Emily","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,23]]},"reference":[{"key":"157_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00039-017-0396-9","volume":"27","author":"N Alon","year":"2017","unstructured":"Alon, N.: Asymptotically optimal induced universal graphs. Geom. Funct. Anal. 27, 1\u201332 (2017)","journal-title":"Geom. Funct. Anal."},{"unstructured":"Alon, N.: Personal communication (2023)","key":"157_CR2"},{"key":"157_CR3","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.dam.2019.01.032","volume":"260","author":"P Balister","year":"2019","unstructured":"Balister, P., Bollob\u00e1s, B., Sahasrabudhe, J., Veremyev, A.: Dense subgraphs in random graphs. Discret. Appl. Math. 260, 66\u201374 (2019)","journal-title":"Discret. Appl. Math."},{"key":"157_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"key":"157_CR5","doi-asserted-by":"publisher","first-page":"996","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 Bioinform. 14, 996\u20131010 (2013)","journal-title":"BMC Bioinform."},{"key":"157_CR6","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.jctb.2023.01.001","volume":"160","author":"S Chatterjee","year":"2023","unstructured":"Chatterjee, S., Diaconis, P.: Isomorphisms between random graphs. J. Comb. Theory Ser. B 160, 144\u2013162 (2023)","journal-title":"J. Comb. Theory Ser. B"},{"key":"157_CR7","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. Int. J. Pattern Recognit. Artif. Intell. 18, 265\u2013298 (2004)","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"key":"157_CR8","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1613\/jair.43","volume":"1","author":"DJ Cook","year":"1994","unstructured":"Cook, D.J., Holder, L.B.: Substructure discovery using minimum description length and background knowledge. J. Artif. Intell. Res. 1, 231\u2013255 (1994)","journal-title":"J. Artif. Intell. Res."},{"key":"157_CR9","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 nd open combinatorial maps. Comput. Vis. Image Underst. 115, 996\u20131010 (2011)","journal-title":"Comput. Vis. Image Underst."},{"key":"157_CR10","first-page":"68","volume":"1","author":"H-C 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, 68\u201379 (2011)","journal-title":"Wiley Interdiscip. Rev.: Comput. Mol. Sci."},{"key":"157_CR11","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01895716","volume":"14","author":"P Erd\u0151s","year":"1963","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: Asymmetric graphs. Acta Math. Hung. 14, 295\u2013315 (1963)","journal-title":"Acta Math. Hung."},{"key":"157_CR12","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.ejc.2013.06.012","volume":"35","author":"N Fountoulakis","year":"2014","unstructured":"Fountoulakis, N., Kang, R.J., McDiarmid, C.: Largest sparse subgraphs of random graphs. Eur. J. Comb. 35, 232\u2013244 (2014)","journal-title":"Eur. J. Comb."},{"key":"157_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0076911","volume":"8","author":"R Giugno","year":"2013","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, 1\u201311 (2013)","journal-title":"PLoS ONE"},{"unstructured":"Janson, S.: Personal communication (2022)","key":"157_CR14"},{"key":"157_CR15","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random Graphs. Wiley-Interscience, New York (2000)"},{"key":"157_CR16","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1002\/rsa.10054","volume":"21","author":"JH Kim","year":"2002","unstructured":"Kim, J.H., Sudakov, B., Vu, V.H.: On the asymmetry of random regular graphs and random graphs. Random Struct. Algorithms 21, 216\u2013224 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"157_CR17","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1613\/jair.5768","volume":"61","author":"C McCreesh","year":"2018","unstructured":"McCreesh, C., Prosser, P., Solnon, C., Trimble, J.: When subgraph isomorphism is really hard, and why this matters for graph databases. J. Artif. Intell. Res. 61, 723\u2013759 (2018)","journal-title":"J. Artif. Intell. Res."},{"unstructured":"McCreesh, C., Prosser, P., Trimble, J.: Heuristics and really hard instances for subgraph isomorphism problems. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI\u201916), pp. 631\u2013638. AAAI Press, New York (2016)","key":"157_CR18"},{"key":"157_CR19","doi-asserted-by":"publisher","first-page":"1573","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, 1573\u20134951 (2002)","journal-title":"J. Comput. Aided Mol. Des."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00157-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00157-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00157-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T12:38:50Z","timestamp":1757075930000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00157-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,23]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["157"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00157-z","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,6,23]]},"assertion":[{"value":"15 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"35"}}