{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T09:30:29Z","timestamp":1743067829892,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531730"},{"type":"electronic","value":"9783662531747"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_21","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T10:50:06Z","timestamp":1470307806000},"page":"299-311","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Induced Minor Free Graphs: Isomorphism and Clique-width"],"prefix":"10.1007","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"key":"21_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/3-540-36136-7_5","volume-title":"Algorithms and Computation","author":"R Boliac","year":"2002","unstructured":"Boliac, R., Lozin, V.V.: On the Clique-width of graphs in hereditary classes. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 44\u201354. Springer, Heidelberg (2002)"},{"key":"21_CR2","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":"4","key":"21_CR3","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":"21_CR4","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":"21_CR5","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. Theor. Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theor. Comput. Syst."},{"key":"21_CR6","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":"21_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/978-3-319-08783-2_42","volume-title":"Computing and Combinatorics","author":"KK Dabrowski","year":"2014","unstructured":"Dabrowski, K.K., Paulusma, D.: Classifying the clique-width of H-Free bipartite graphs. In: Cai, Z., Zelikovsky, A., Bourgeois, A. (eds.) COCOON 2014. LNCS, vol. 8591, pp. 489\u2013500. Springer, Heidelberg (2014)"},{"key":"21_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-319-18173-8_12","volume-title":"Algorithms and Complexity","author":"KK Dabrowski","year":"2015","unstructured":"Dabrowski, K.K., Paulusma, D.: Clique-width of graph classes defined by two forbidden induced subgraphs. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 167\u2013181. Springer, Heidelberg (2015)"},{"key":"21_CR9","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":"21_CR10","volume-title":"Graph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, Electronic edn. Springer, Heidelberg (2005)","edition":"Electronic"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Grohe, M., Marx, D.: Structure theorem and isomorphism test for graphs with excluded topological subgraphs. In: STOC, pp. 173\u2013192 (2012)","DOI":"10.1145\/2213977.2213996"},{"key":"21_CR12","unstructured":"Grohe, M., Schweitzer, P.: Isomorphism testing for graphs of bounded rank width. CoRR, abs\/1505.03737 (2015). \n                      http:\/\/arxiv.org\/abs\/1208.0142"},{"issue":"3","key":"21_CR13","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":"21_CR14","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Isomorphism of planar graphs. In: Complexity of Computer Computations, pp. 131\u2013152 (1972)","DOI":"10.1007\/978-1-4684-2001-2_13"},{"key":"21_CR15","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":"21_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-642-13731-0_9","volume-title":"Algorithm Theory - SWAT 2010","author":"S Kratsch","year":"2010","unstructured":"Kratsch, S., Schweitzer, P.: Isomorphism for graphs of bounded feedback vertex set number. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 81\u201392. Springer, Heidelberg (2010)"},{"key":"21_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-34611-8_7","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S Kratsch","year":"2012","unstructured":"Kratsch, S., Schweitzer, P.: Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol. 7551, pp. 34\u201345. Springer, Heidelberg (2012)"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. In: FOCS 2014, pp. 186\u2013195 (2014)","DOI":"10.1109\/FOCS.2014.28"},{"key":"21_CR19","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."},{"key":"21_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-642-45030-3_11","volume-title":"Algorithms and Computation","author":"Y Otachi","year":"2013","unstructured":"Otachi, Y., Schweitzer, P.: Isomorphism on subgraph-closed graph classes: a complexity dichotomy and intermediate graph classes. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) ISAAC 2013. LNCS, vol. 8283, pp. 111\u2013118. Springer, Heidelberg (2013)"},{"key":"21_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/978-3-319-08404-6_32","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"Y Otachi","year":"2014","unstructured":"Otachi, Y., Schweitzer, P.: Reduction techniques for graph isomorphism in the context of width parameters. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 368\u2013379. Springer, Heidelberg (2014)"},{"issue":"1","key":"21_CR22","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. Theor. Ser. B 95(1), 79\u2013100 (2005)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"4","key":"21_CR23","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. Theor. Ser. B 96(4), 514\u2013528 (2006)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"21_CR24","first-page":"147","volume":"174","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 (1988). Russian. English Translation in Journal of Soviet Mathematics 55, 1621\u20131643 (1991)","journal-title":"Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta"},{"key":"21_CR25","unstructured":"Schweitzer, P.: Towards an isomorphism dichotomy for hereditary graph classes. In: STACS, vol. 30, pp. 689\u2013702 (2015)"},{"key":"21_CR26","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1016\/j.dam.2010.05.005","volume":"160","author":"P Hof van\u2019t","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":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T01:12:08Z","timestamp":1558314728000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"5 August 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Garching","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2015","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2015","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2015","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"41","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2015","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}