{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:50Z","timestamp":1759637630976},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450297"},{"type":"electronic","value":"9783642450303"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45030-3_11","type":"book-chapter","created":{"date-parts":[[2013,12,11]],"date-time":"2013-12-11T21:32:52Z","timestamp":1386797572000},"page":"111-118","source":"Crossref","is-referenced-by-count":3,"title":["Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes"],"prefix":"10.1007","author":[{"given":"Yota","family":"Otachi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","first-page":"1447","volume-title":"Handbook of Combinatorics","author":"L. Babai","year":"1995","unstructured":"Babai, L.: Automorphism groups, isomorphism, reconstruction. In: Handbook of Combinatorics, vol.\u00a02, pp. 1447\u20131540. MIT Press, Cambridge (1995)"},{"key":"11_CR2","unstructured":"Booth, K.S., Colbourn, C.J.: Problems polynomially equivalent to graph isomorphism. Technical Report CS-77-04, Comput. Sci. Dep., Univ. Waterloo (1979)"},{"issue":"1","key":"11_CR3","first-page":"157","volume":"15","author":"A.R. Curtis","year":"2013","unstructured":"Curtis, A.R., Lin, M.C., McConnell, R.M., Nussbaum, Y., Soulignac, F.J., Spinrad, J., Szwarcfiter, J.L.: Isomorphism of graph classes related to the circular-ones property. Discrete Mathematics & Theoretical Computer Science\u00a015(1), 157\u2013182 (2013)","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Fixed-point definability and polynomial time on graphs with excluded minors. In: LICS, pp. 179\u2013188 (2010)","DOI":"10.1109\/LICS.2010.22"},{"key":"11_CR5","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":"11_CR6","doi-asserted-by":"crossref","unstructured":"K\u00f6bler, J., Kuhnert, S., Verbitsky, O.: Helly circular-arc graph isomorphism is in logspace. In: Electronic Colloquium on Computational Complexity, ECCC (2013)","DOI":"10.1007\/978-3-642-40313-2_56"},{"key":"11_CR7","doi-asserted-by":"publisher","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 (1993)"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Schweitzer, P.: Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. In: WG, pp. 34\u201345 (2012)","DOI":"10.1007\/978-3-642-34611-8_7"},{"issue":"1","key":"11_CR9","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. ACM\u00a022(1), 155\u2013171 (1975)","journal-title":"J. ACM"},{"issue":"2","key":"11_CR10","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"G.S. Lueker","year":"1979","unstructured":"Lueker, G.S., Booth, K.S.: A linear time algorithm for deciding interval graph isomorphism. J. ACM\u00a026(2), 183\u2013195 (1979)","journal-title":"J. ACM"},{"key":"11_CR11","unstructured":"Papadimitriou, C.H.: Computational complexity. Addison-Wesley (1994)"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Ponomarenko, I.N.: The isomorphism problem for classes of graphs that are invariant with respect to contraction. Zap. Nauchn. Sem. LOMI\u00a0174, 147\u2013177 (1988) Russian. English translation in J. Soviet Math. 55, 1621\u20131643 (1991)","DOI":"10.1007\/BF01098279"},{"key":"11_CR13","unstructured":"Schweitzer, P.: Problems of unknown complexity: Graph isomorphism and Ramsey theoretic numbers. PhD thesis, Universit\u00e4t des Saarlandes, Germany (2009)"},{"issue":"1","key":"11_CR14","doi-asserted-by":"publisher","first-page":"60","DOI":"10.3390\/a6010060","volume":"6","author":"R. Uehara","year":"2013","unstructured":"Uehara, R.: Tractabilities and intractabilities on geometric intersection graphs. Algorithms\u00a06(1), 60\u201383 (2013)","journal-title":"Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45030-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T06:26:39Z","timestamp":1558765599000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45030-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450297","9783642450303"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45030-3_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}