{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T18:48:35Z","timestamp":1710269315703},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,6,21]],"date-time":"2017-06-21T00:00:00Z","timestamp":1498003200000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00224-017-9775-8","type":"journal-article","created":{"date-parts":[[2017,6,21]],"date-time":"2017-06-21T06:16:10Z","timestamp":1498025770000},"page":"1084-1127","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Towards an Isomorphism Dichotomy for Hereditary Graph Classes"],"prefix":"10.1007","volume":"61","author":[{"given":"Pascal","family":"Schweitzer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,21]]},"reference":[{"key":"9775_CR1","volume-title":"FSTTCS, pp. 327\u2013337","author":"V Arvind","year":"2010","unstructured":"Arvind, V., Das, B., K\u00f6bler, J., Toda, S.: Colored hypergraph isomorphism is fixed parameter tractable. In: FSTTCS, pp. 327\u2013337 (2010)"},{"key":"9775_CR2","volume-title":"FCT, pp. 34\u201350","author":"L Babai","year":"1981","unstructured":"Babai, L.: Moderately exponential bound for graph isomorphism. In: FCT, pp. 34\u201350 (1981)"},{"key":"9775_CR3","unstructured":"Babai, L.: Automorphism groups, isomorphism, reconstruction. Handbook of Combinatorics, vol 2, pp. 1447\u20131540. MIT Press (1995)"},{"key":"9775_CR4","volume-title":"STOC, pp. 684\u2013697. ACM","author":"L Babai","year":"2016","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In: STOC, pp. 684\u2013697. ACM (2016)"},{"key":"9775_CR5","volume-title":"STOC, pp. 171\u2013183","author":"L Babai","year":"1983","unstructured":"Babai, L., Luks, E.M.: Canonical labeling of graphs. In: STOC, pp. 171\u2013183 (1983)"},{"key":"9775_CR6","doi-asserted-by":"crossref","unstructured":"Bacs\u00f3, G., Tuza, Z.: Dominating cliques in P 5 , $P_{5},$ -free graphs. Period. Math Hungar. 21(4), 303\u2013308 (1990)","DOI":"10.1007\/BF02352694"},{"key":"9775_CR7","unstructured":"Bandelt, H.-J., Mulder, H.M.: Distance-hereditary graphs. J. Combinatorial Theory Ser. B 41(2), 182\u2013208 (1986)"},{"key":"9775_CR8","unstructured":"Booth, K.S., Colbourn, C.J., Problems Polynomially Equivalent to Graph Isomorphism. Technical Report CS-77-04, Comp. Sci. Dep., Univ. Waterloo (1979)"},{"issue":"2","key":"9775_CR9","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.dam.2004.01.009","volume":"145","author":"A Brandst\u00e4dt","year":"2005","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On the structure of (P 5 $_{5}$ , gem)-free graphs. Discret. Appl. Math. 145(2), 155\u2013166 (2005)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"9775_CR10","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1008605.1008608","volume":"10","author":"MJ Colbourn","year":"1978","unstructured":"Colbourn, M.J., Colbourn, C.J.: Graph isomorphism and self-complementary graphs. SIGACT News 10(1), 25\u201329 (1978)","journal-title":"SIGACT News"},{"key":"9775_CR11","unstructured":"Curtis, A., Lin, M., McConnell, R., Nussbaum, Y., Soulignac, F., Spinrad, J., Szwarcfiter, J.: Isomorphism of graph classes related to the circular-ones property. Discret. Math. Theor. Comput. Sci. 15(1), 157\u2013182 (2013)"},{"issue":"5","key":"9775_CR12","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1093\/comjnl\/bxv096","volume":"59","author":"K Dabrowski","year":"2016","unstructured":"Dabrowski, K., Paulusma, D., Clique-width of graph classes defined by two forbidden induced subgraphs. Comput. J. 59(5), 650\u2013666 (2016)","journal-title":"Comput. J."},{"issue":"0","key":"9775_CR13","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.tcs.2013.12.004","volume":"522","author":"KK Dabrowski","year":"2014","unstructured":"Dabrowski, K.K., Golovach, P.A., Paulusma, D.: Colouring of graphs with ramsey-type forbidden subgraphs. Theor. Comput. Sci. 522, 34\u201343 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9775_CR14","volume-title":"Fixed-parameter tractability of the graph isomorphism and canonization problems","author":"F Fuhlbr\u00fcck","year":"2013","unstructured":"Fuhlbr\u00fcck, F.: Fixed-Parameter Tractability of the Graph Isomorphism and Canonization Problems. Diploma thesis, Humboldt-Universit\u00e4t zu Berlin (2013)"},{"issue":"3","key":"9775_CR15","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0166-218X(83)90078-1","volume":"6","author":"MK Goldberg","year":"1983","unstructured":"Goldberg, M.K.: A nonfactorial algorithm for testing isomorphism of two graphs. Discret. Appl. Math. 6(3), 229\u2013236 (1983)","journal-title":"Discret. Appl. Math."},{"key":"9775_CR16","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.dam.2013.10.010","volume":"166","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Paulusma, D.: List coloring in the absence of two subgraphs. Discret. Appl. Math. 166, 123\u2013130 (2014)","journal-title":"Discret. Appl. Math."},{"key":"9775_CR17","doi-asserted-by":"crossref","unstructured":"Grohe, M., Marx, D.: Structure theorem and isomorphism test for graphs with excluded topological subgraphs (2012)","DOI":"10.1145\/2213977.2213996"},{"key":"9775_CR18","doi-asserted-by":"crossref","unstructured":"Grohe, M., Schweitzer, P.: Isomorphism testing for graphs of bounded rank width. In: FOCS, pp 1010\u20131029. IEEE Computer Society (2015)","DOI":"10.1109\/FOCS.2015.66"},{"key":"9775_CR19","unstructured":"Gurevich, Y.: From Invariants to Canonization. Bulletin of the EATCS, 63 (1997)"},{"key":"9775_CR20","doi-asserted-by":"crossref","unstructured":"Gurevich, Y.: From invariants to canonization. In: Current Trends in Theoretical Computer Science, pp. 327\u2013331. World Scientific (2001)","DOI":"10.1142\/9789812810403_0003"},{"issue":"1","key":"9775_CR21","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.cosrev.2010.01.001","volume":"4","author":"M Habib","year":"2010","unstructured":"Habib, M., Paul, C.: A survey of the algorithmic aspects of modular decomposition. Comput. Sci. Rev. 4(1), 41\u201359 (2010)","journal-title":"Computer Science Review"},{"key":"9775_CR22","doi-asserted-by":"crossref","unstructured":"Junttila, T.A., Kaski, P.: Conflict propagation and component recursion for canonical labeling. In: TAPAS, pp. 151\u2013162 (2011)","DOI":"10.1007\/978-3-642-19754-3_16"},{"key":"9775_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The graph isomorphism problem: Its structural complexity","author":"J K\u00f6bler","year":"1993","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The Graph Isomorphism Problem: Its Structural Complexity. Birkh\u00e4user Verlag, Basel, Switzerland (1993)"},{"key":"9775_CR24","doi-asserted-by":"crossref","unstructured":"Ko\u0307bler, J., Verbitsky, O.: From invariants to canonization in parallel. In: CSR, pp. 216\u2013227 (2008)","DOI":"10.1007\/978-3-540-79709-8_23"},{"key":"9775_CR25","doi-asserted-by":"crossref","unstructured":"Kr\u00e1l, D., Kratochv\u00edl, J., Tuza, Z., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. In: WG, pp. 254\u2013262 (2001)","DOI":"10.1007\/3-540-45477-2_23"},{"key":"9775_CR26","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Schweitzer, P.: Graph isomorphism for graph classes characterized by two forbidden induced subgraphs (2012)","DOI":"10.1007\/978-3-642-34611-8_7"},{"key":"9775_CR27","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/j.dam.2014.10.026","volume":"216","author":"S Kratsch","year":"2017","unstructured":"Kratsch, S., Schweitzer, P.: Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. Discret. Appl. Math. 216, 240\u2013253 (2017)","journal-title":"Discret. Appl. Math."},{"issue":"44\u201346","key":"9775_CR28","doi-asserted-by":"crossref","first-page":"4023","DOI":"10.1016\/j.tcs.2010.08.027","volume":"411","author":"VV Lozin","year":"2010","unstructured":"Lozin, V.V.: A decidability result for the dominating set problem. Theor. Comput. Sci. 411(44\u201346), 4023\u20134027 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9775_CR29","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"EM Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25(1), 42\u201365 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"9775_CR30","doi-asserted-by":"crossref","unstructured":"Miller, G.L.: Isomorphism testing and canonical forms for k-contractable graphs (a generalization of bounded valence and bounded genus). In: FCT, pp. 310\u2013327 (1983)","DOI":"10.1007\/3-540-12689-9_114"},{"issue":"3","key":"9775_CR31","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/s11390-009-9242-3","volume":"24","author":"S-i Nakano","year":"2009","unstructured":"Nakano, S.-i., Uehara, R., Uno, T.: A new approach to graph recognition and applications to distance-hereditary graphs. J. Comput. Sci. Technol. 24(3), 517\u2013533 (2009)","journal-title":"J. Comput. Sci. Technol."},{"key":"9775_CR32","doi-asserted-by":"crossref","unstructured":"Otachi, Y., Schweitzer, P.: Isomorphism on subgraph-closed graph classes: A complexity dichotomy and intermediate graph classes. In: ISAAC, pp. 111\u2013118 (2013)","DOI":"10.1007\/978-3-642-45030-3_11"},{"key":"9775_CR33","unstructured":"Rao, M.: Decomposition of (gem,co-gem)-free graphs. Unpublished available at http:\/\/www.labri.fr\/perso\/rao\/publi\/decompgemcogem.ps (2007)"},{"key":"9775_CR34","volume-title":"Problems of unknown complexity: Graph isomorphism and Ramsey theoretic numbers. PhD thesis","author":"P Schweitzer","year":"2009","unstructured":"Schweitzer, P.: Problems of Unknown Complexity: Graph isomorphism and Ramsey Theoretic Numbers. PhD thesis. Universit\u00e4t des Saarlandes, Germany (2009)"},{"key":"9775_CR35","unstructured":"Schweitzer, P.: Towards an isomorphism dichotomy for hereditary graph classes. In: Mayr, E. W., Ollinger, N. (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pp. 689\u2013702. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)"},{"key":"9775_CR36","doi-asserted-by":"crossref","unstructured":"Seress, \u00c1.: Permutation Group Algorithms. Cambridge Tracts in Mathematics. Cambridge University Press (2003)","DOI":"10.1017\/CBO9780511546549"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9775-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9775-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9775-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T12:09:42Z","timestamp":1569499782000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9775-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,21]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["9775"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9775-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,21]]}}}