{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:49Z","timestamp":1771036369592,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2020,7,2]],"date-time":"2020-07-02T00:00:00Z","timestamp":1593648000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,2]],"date-time":"2020-07-02T00:00:00Z","timestamp":1593648000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"NWO","award":["NETWORKS"],"award-info":[{"award-number":["NETWORKS"]}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP24106004"],"award-info":[{"award-number":["JP24106004"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP18K11168"],"award-info":[{"award-number":["JP18K11168"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP18K11169"],"award-info":[{"award-number":["JP18K11169"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP18H04091"],"award-info":[{"award-number":["JP18H04091"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP18H06469"],"award-info":[{"award-number":["JP18H06469"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP15K00009"],"award-info":[{"award-number":["JP15K00009"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"crossref","award":["JPMJCR1402"],"award-info":[{"award-number":["JPMJCR1402"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012012","name":"Kanamori Foundation","doi-asserted-by":"crossref","award":["Informational Science Advancement"],"award-info":[{"award-number":["Informational Science Advancement"]}],"id":[{"id":"10.13039\/501100012012","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00453-020-00737-z","type":"journal-article","created":{"date-parts":[[2020,7,2]],"date-time":"2020-07-02T08:30:58Z","timestamp":1593678658000},"page":"3566-3587","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Subgraph Isomorphism on Graph Classes that Exclude a Substructure"],"prefix":"10.1007","volume":"82","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tesshu","family":"Hanaka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuaki","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0087-853X","authenticated-orcid":false,"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom C.","family":"van der Zanden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,2]]},"reference":[{"issue":"4","key":"737_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995). https:\/\/doi.org\/10.1145\/210332.210337","journal-title":"J. ACM"},{"key":"737_CR2","first-page":"13","volume":"1","author":"CA Barefoot","year":"1987","unstructured":"Barefoot, C.A., Entringer, R.C., Swart, H.C.: Vulnerability in graphs\u2014a comparative survey. J. Combin. Math. Combin. Comput. 1, 13\u201322 (1987)","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"737_CR3","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L, Nederlof, J., van der Zanden, T.C.: Subexponential time algorithms for embedding $$H$$-minor free graphs. In: ICALP 2016, vol. 55. LIPIcs, pp. 9:1\u20139:14 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.9","DOI":"10.4230\/LIPIcs.ICALP.2016.9"},{"key":"737_CR4","doi-asserted-by":"publisher","unstructured":"Bonsma, P.S.: Surface split decompositions and subgraph isomorphism in graphs on surfaces. In: STACS 2012, vol. 14. LIPIcs, pp. 531\u2013542 (2012). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2012.531","DOI":"10.4230\/LIPIcs.STACS.2012.531"},{"issue":"3","key":"737_CR5","doi-asserted-by":"publisher","first-page":"18:1","DOI":"10.1145\/3051094","volume":"64","author":"M Cygan","year":"2017","unstructured":"Cygan, M., Fomin, F.V., Golovnev, A., Kulikov, A.S., Mihajlin, I., Pachocki, J., Soca\u0142a, A.: Tight lower bounds on graph embedding problems. J. ACM 64(3), 18:1\u201318:22 (2017). https:\/\/doi.org\/10.1145\/3051094","journal-title":"J. ACM"},{"key":"737_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, New York (2015)"},{"key":"737_CR7","doi-asserted-by":"publisher","unstructured":"Damaschke, P.: Induced subgraph isomorphism for cographs in NP-complete. In: WG 1990, vol. 484. LNCS, pp. 72\u201378 (1990). https:\/\/doi.org\/10.1007\/3-540-53832-1_32","DOI":"10.1007\/3-540-53832-1_32"},{"key":"737_CR8","doi-asserted-by":"publisher","unstructured":"Dorn, F.: Planar subgraph isomorphism revisited. In: STACS 2010, vol. 5. LIPIcs, pp. 263\u2013274 (2010). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2010.2460","DOI":"10.4230\/LIPIcs.STACS.2010.2460"},{"issue":"1&2","key":"737_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci. 141(1&2), 109\u2013131 (1995). https:\/\/doi.org\/10.1016\/0304-3975(94)00097-3","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"737_CR10","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1007\/s00453-016-0127-x","volume":"76","author":"PG Drange","year":"2016","unstructured":"Drange, P.G., Dregi, M.S., van\u2019t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. Algorithmica 76(4), 1181\u20131202 (2016). https:\/\/doi.org\/10.1007\/s00453-016-0127-x","journal-title":"Algorithmica"},{"issue":"3","key":"737_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Gr. Algorithms Appl. 3(3), 1\u201327 (1999). https:\/\/doi.org\/10.7155\/jgaa.00014","journal-title":"J. Gr. Algorithms Appl."},{"issue":"3","key":"737_CR12","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/BF01190507","volume":"13","author":"MR Fellows","year":"1995","unstructured":"Fellows, M.R., Kratochv\u00edl, J., Middendorf, M., Pfeiffer, F.: The complexity of induced minors and related problems. Algorithmica 13(3), 266\u2013282 (1995). https:\/\/doi.org\/10.1007\/BF01190507","journal-title":"Algorithmica"},{"issue":"1","key":"737_CR13","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49\u201365 (1987). https:\/\/doi.org\/10.1007\/BF02579200","journal-title":"Combinatorica"},{"issue":"2","key":"737_CR14","first-page":"77","volume":"17","author":"R Ganian","year":"2015","unstructured":"Ganian, R.: Improving vertex cover as a graph parameter. Discrete Math. Theor. Comput. Sci. 17(2), 77\u2013100 (2015)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"737_CR15","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, New York (1979)"},{"issue":"1&2","key":"737_CR16","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(96)00046-1","volume":"164","author":"A Gupta","year":"1996","unstructured":"Gupta, A., Nishimura, N.: The complexity of subgraph isomorphism for classes of partial $$k$$-trees. Theor. Comput. Sci. 164(1&2), 287\u2013298 (1996). https:\/\/doi.org\/10.1016\/0304-3975(96)00046-1","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"737_CR17","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1016\/j.jcss.2007.01.003","volume":"73","author":"MT Hajiaghayi","year":"2007","unstructured":"Hajiaghayi, M.T., Nishimura, N.: Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth. J. Comput. Syst. Sci. 73(5), 755\u2013768 (2007). https:\/\/doi.org\/10.1016\/j.jcss.2007.01.003","journal-title":"J. Comput. Syst. Sci."},{"key":"737_CR18","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1137\/1.9781611973730.42","volume":"2015","author":"BMP Jansen","year":"2015","unstructured":"Jansen, B.M.P., Marx, D.: Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and turing kernels. SODA 2015, 616\u2013629 (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.42","journal-title":"SODA"},{"issue":"3","key":"737_CR19","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987). https:\/\/doi.org\/10.1287\/moor.12.3.415","journal-title":"Math. Oper. Res."},{"issue":"21","key":"737_CR20","doi-asserted-by":"publisher","first-page":"3164","DOI":"10.1016\/j.disc.2012.07.010","volume":"312","author":"S Kijima","year":"2012","unstructured":"Kijima, S., Otachi, Y., Saitoh, T., Uno, T.: Subgraph isomorphism in graph classes. Discrete Math. 312(21), 3164\u20133173 (2012). https:\/\/doi.org\/10.1016\/j.disc.2012.07.010","journal-title":"Discrete Math."},{"issue":"9","key":"737_CR21","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1016\/j.ipl.2016.04.006","volume":"116","author":"M Kiyomi","year":"2016","unstructured":"Kiyomi, M., Otachi, Y.: Finding a chain graph in a bipartite permutation graph. Inf. Process. Lett. 116(9), 569\u2013573 (2016). https:\/\/doi.org\/10.1016\/j.ipl.2016.04.006","journal-title":"Inf. Process. Lett."},{"key":"737_CR22","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.dam.2015.01.040","volume":"199","author":"M Konagaya","year":"2016","unstructured":"Konagaya, M., Otachi, Y., Uehara, R.: Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs. Discrete Appl. Math. 199, 37\u201345 (2016). https:\/\/doi.org\/10.1016\/j.dam.2015.01.040","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"737_CR23","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00453-011-9554-x","volume":"64","author":"M Lampis","year":"2012","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64(1), 19\u201337 (2012). https:\/\/doi.org\/10.1007\/s00453-011-9554-x","journal-title":"Algorithmica"},{"issue":"4","key":"737_CR24","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983). https:\/\/doi.org\/10.1287\/moor.8.4.538","journal-title":"Math. Oper. Res."},{"issue":"3","key":"737_CR25","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0304-3975(89)90011-X","volume":"63","author":"A Lingas","year":"1989","unstructured":"Lingas, A.: Subgraph isomorphism for biconnected outerplanar graphs in cubic time. Theor. Comput. Sci. 63(3), 295\u2013302 (1989). https:\/\/doi.org\/10.1016\/0304-3975(89)90011-X","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"737_CR26","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.ipl.2003.09.016","volume":"89","author":"D Marx","year":"2004","unstructured":"Marx, D.: List edge multicoloring in graphs with few cycles. Inf. Process. Lett. 89(2), 85\u201390 (2004). https:\/\/doi.org\/10.1016\/j.ipl.2003.09.016","journal-title":"Inf. Process. Lett."},{"key":"737_CR27","doi-asserted-by":"publisher","unstructured":"Marx, D., Pilipczuk, M.: Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). In: STACS 2014, vol. 25. LIPIcs, pp. 542\u2013553 (2014). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2014.542","DOI":"10.4230\/LIPIcs.STACS.2014.542"},{"issue":"1\u20133","key":"737_CR28","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J., Thomas, R.: On the complexity of finding iso- and other morphisms for partial $$k$$-trees. Discrete Math. 108(1\u20133), 343\u2013364 (1992). https:\/\/doi.org\/10.1016\/0012-365X(92)90687-B","journal-title":"Discrete Math."},{"key":"737_CR29","series-title":"Annals of Discrete Mathematics","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0167-5060(08)70324-8","volume-title":"Algorithmic Aspects of Combinatorics","author":"DW Matula","year":"1978","unstructured":"Matula, D.W.: Subtree isomorphism in $${O(n^{5\/2})}$$. In: Alspach, B., Hell, P., Miller, D.J. (eds.) Algorithmic Aspects of Combinatorics. Annals of Discrete Mathematics, vol. 2, pp. 91\u2013106. Elsevier, Amsterdam (1978)"},{"issue":"1\u20133","key":"737_CR30","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201(1\u20133), 189\u2013241 (1999). https:\/\/doi.org\/10.1016\/S0012-365X(98)00319-7","journal-title":"Discrete Math."},{"issue":"1","key":"737_CR31","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105\u2013113 (1987). https:\/\/doi.org\/10.1007\/BF02579206","journal-title":"Combinatorica"},{"key":"737_CR32","doi-asserted-by":"publisher","unstructured":"Nesetril, J., de Mendez, P.O.: Sparsity-Graphs, Structures, and Algorithms, vol 28. Algorithms and Combinatorics. Springer, New York (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4","DOI":"10.1007\/978-3-642-27875-4"},{"issue":"2","key":"737_CR33","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae 15(2), 307\u2013309 (1974)","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"737_CR34","doi-asserted-by":"publisher","unstructured":"Tedder, M., Corneil, D.G, Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: ICALP 2008 (1), vol. 5125. LNCS, pp. 634\u2013645 (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_52","DOI":"10.1007\/978-3-540-70575-8_52"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00737-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00737-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00737-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,2]],"date-time":"2021-07-02T00:05:59Z","timestamp":1625184359000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00737-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,2]]},"references-count":34,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["737"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00737-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,2]]},"assertion":[{"value":"28 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}