{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:14Z","timestamp":1759638794592,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,10,24]],"date-time":"2016-10-24T00:00:00Z","timestamp":1477267200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,10,24]],"date-time":"2016-10-24T00:00:00Z","timestamp":1477267200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["25730003"],"award-info":[{"award-number":["25730003"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00453-016-0234-8","type":"journal-article","created":{"date-parts":[[2016,10,24]],"date-time":"2016-10-24T12:47:41Z","timestamp":1477313261000},"page":"29-47","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Induced Minor Free Graphs: Isomorphism and Clique-Width"],"prefix":"10.1007","volume":"80","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","affiliation":[]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,24]]},"reference":[{"key":"234_CR1","doi-asserted-by":"crossref","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time. CoRR, abs\/1512.03547 (To appear in STOC 2016) (2015)","DOI":"10.1145\/2897518.2897542"},{"key":"234_CR2","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.endm.2015.06.029","volume":"49","author":"J B\u0142asiok","year":"2015","unstructured":"B\u0142asiok, J., Kami\u0144ski, M., Raymond, J.-F., Trunck, T.: Induced minors and well-quasi-ordering. Electr. Notes Discrete Math. 49, 197\u2013201 (2015)","journal-title":"Electr. Notes Discrete Math."},{"key":"234_CR3","doi-asserted-by":"crossref","unstructured":"Boliac, R., Lozin, V.V.: On the clique-width of graphs in hereditary classes. In: ISAAC 2002, vol. 2518 of Lecture Notes in Computer Science, pp. 44\u201354 (2002)","DOI":"10.1007\/3-540-36136-7_5"},{"key":"234_CR4","unstructured":"Booth, K.S., Colbourn, C.J.: Problems polynomially equivalent to graph isomorphism. Technical Report CS-77-04, Computer Science Department, University of Waterloo (1979)"},{"issue":"1","key":"234_CR5","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1002\/net.3230110103","volume":"11","author":"CJ Colbourn","year":"1981","unstructured":"Colbourn, C.J.: On testing isomorphism of permutation graphs. Networks 11(1), 13\u201321 (1981)","journal-title":"Networks"},{"issue":"4","key":"234_CR6","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"DG Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825\u2013847 (2005)","journal-title":"SIAM J. Comput."},{"key":"234_CR7","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.ipl.2013.09.012","volume":"114","author":"B Courcelle","year":"2014","unstructured":"Courcelle, B.: Clique-width and edge contraction. Inf. Process. Lett. 114, 42\u201344 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"234_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"key":"234_CR9","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101, 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"234_CR10","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.dam.2015.06.030","volume":"200","author":"KK Dabrowski","year":"2016","unstructured":"Dabrowski, K.K., Paulusma, D.: Classifying the clique-width of $$H$$-free bipartite graphs. Discrete Appl. Math. 200, 43\u201351 (2016)","journal-title":"Discrete Appl. Math."},{"key":"234_CR11","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1093\/comjnl\/bxv096","volume":"59","author":"KK Dabrowski","year":"2016","unstructured":"Dabrowski, K.K., Paulusma, D.: Clique-width of graph classes defined by two forbidden induced subgraphs. Comput. J. 59, 650\u2013666 (2016)","journal-title":"Comput. J."},{"key":"234_CR12","doi-asserted-by":"crossref","unstructured":"Datta, S., Limaye, N., Nimbhorkar, P., Thierauf, T., Wagner, F.: Planar graph isomorphism is in log-space. In: IEEE Conference on Computational Complexity, pp. 203\u2013214 (2009)","DOI":"10.1109\/CCC.2009.16"},{"key":"234_CR13","unstructured":"de\u00a0Ridder, H.N., et al.: ISGCI: information system on graph classes and their inclusions\u2014list of small graphs. \n                    http:\/\/graphclasses.org\/smallgraphs.html"},{"key":"234_CR14","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, 266\u2013282 (1995)","journal-title":"Algorithmica"},{"key":"234_CR15","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Golovach, P.A., Thilikos, D.M.: Contraction bidimensionality: the accurate picture. In: ESA 2009, vol. 5757 of Lecture Notes in Computer Science, pp. 706\u2013717 (2009)","DOI":"10.1007\/978-3-642-04128-0_63"},{"issue":"3","key":"234_CR16","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423\u2013443 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"234_CR17","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/120892234","volume":"44","author":"M Grohe","year":"2015","unstructured":"Grohe, M., Marx, D.: Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM J. Comput. 44(1), 114\u2013159 (2015)","journal-title":"SIAM J. Comput."},{"key":"234_CR18","doi-asserted-by":"crossref","unstructured":"Grohe, M., Schweitzer, P.: Isomorphism testing for graphs of bounded rank width. In: Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1010\u20131029. IEEE (2015)","DOI":"10.1109\/FOCS.2015.66"},{"issue":"3","key":"234_CR19","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P Hlinen\u00fd","year":"2008","unstructured":"Hlinen\u00fd, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326\u2013362 (2008)","journal-title":"Comput. J."},{"key":"234_CR20","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Isomorphism of Planar Graphs. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 131\u2013152. Springer, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_13"},{"key":"234_CR21","doi-asserted-by":"publisher","first-page":"2747","DOI":"10.1016\/j.dam.2008.08.022","volume":"157","author":"M Kami\u0144ski","year":"2009","unstructured":"Kami\u0144ski, M., Lozin, V.V., Milani\u010d, M.: Recent developments on graphs of bounded clique-width. Discrete Appl. Math. 157, 2747\u20132761 (2009)","journal-title":"Discrete Appl. Math."},{"key":"234_CR22","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Schweitzer, P.: Isomorphism for graphs of bounded feedback vertex set number. In SWAT 2010, vol. 6139 of Lecture Notes in Computer Science, pp. 81\u201392 (2010)","DOI":"10.1007\/978-3-642-13731-0_9"},{"key":"234_CR23","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Schweitzer, P.: Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. In WG 2012, vol. 7551 of Lecture Notes in Computer Science, pp. 34\u201345 (2012)","DOI":"10.1007\/978-3-642-34611-8_7"},{"key":"234_CR24","first-page":"186","volume":"2014","author":"D Lokshtanov","year":"2014","unstructured":"Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. FOCS 2014, 186\u2013195 (2014)","journal-title":"FOCS"},{"key":"234_CR25","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/S0895480102419755","volume":"18","author":"VV Lozin","year":"2004","unstructured":"Lozin, V.V., Rautenbach, D.: On the band-, tree- and clique-width of graphs with bounded vertex degree. SIAM J. Discrete Math. 18, 195\u2013206 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"234_CR26","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"GS Lueker","year":"1979","unstructured":"Lueker, G.S., Booth, K.S.: A linear time algorithm for deciding interval graph isomorphism. J. ACM 26(2), 183\u2013195 (1979)","journal-title":"J. ACM"},{"key":"234_CR27","doi-asserted-by":"crossref","unstructured":"Otachi, Y., Schweitzer, P.: Isomorphism on subgraph-closed graph classes: a complexity dichotomy and intermediate graph classes. In ISAAC 2013, vol. 8283 of Lecture Notes in Computer Science, pp. 111\u2013118 (2013)","DOI":"10.1007\/978-3-642-45030-3_11"},{"key":"234_CR28","doi-asserted-by":"crossref","unstructured":"Otachi, Y., Schweitzer, P.: Reduction techniques for graph isomorphism in the context of width parameters. In SWAT 2014, vol. 8503 of Lecture Notes in Computer Science, pp. 368\u2013379 (2014)","DOI":"10.1007\/978-3-319-08404-6_32"},{"issue":"1","key":"234_CR29","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","volume":"95","author":"S Oum","year":"2005","unstructured":"Oum, S.: Rank-width and vertex-minors. J. Comb. Theory, Ser. B 95(1), 79\u2013100 (2005)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"234_CR30","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"Oum, S., Seymour, P.D.: Approximating clique-width and branch-width. J. Comb. Theory, Ser. B 96(4), 514\u2013528 (2006)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"1991","key":"234_CR31","first-page":"1621","volume":"55","author":"IN Ponomarenko","year":"1988","unstructured":"Ponomarenko, I.N.: The isomorphism problem for classes of graphs closed under contraction. Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta 174:147\u2013177 (Russian). English translation in. J. Sov. Math. 55(1991), 1621\u20131643 (1988)","journal-title":"J. Sov. Math."},{"issue":"3","key":"234_CR32","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U Sch\u00f6ning","year":"1988","unstructured":"Sch\u00f6ning, U.: Graph isomorphism is in the low hierarchy. J. Comput. Syst. Sci. 37(3), 312\u2013323 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"234_CR33","unstructured":"Schweitzer, P.: Towards an isomorphism dichotomy for hereditary graph classes. In STACS 2015, vol.\u00a030 of LIPIcs, pp. 689\u2013702 (2015)"},{"key":"234_CR34","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1016\/j.dam.2010.05.005","volume":"160","author":"P van \u2019t Hof","year":"2012","unstructured":"van \u2019t Hof, P., Kami\u0144ski, M., Paulusma, D., Szeider, S., Thilikos, D.M.: On graph contractions and induced minors. Discrete Appl. Math. 160, 799\u2013809 (2012)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0234-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0234-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0234-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:25:54Z","timestamp":1589696754000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0234-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,24]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["234"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0234-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,10,24]]},"assertion":[{"value":"5 August 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}