{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:07Z","timestamp":1759638247084},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642346101"},{"type":"electronic","value":"9783642346118"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34611-8_7","type":"book-chapter","created":{"date-parts":[[2012,10,22]],"date-time":"2012-10-22T04:42:25Z","timestamp":1350880945000},"page":"34-45","source":"Crossref","is-referenced-by-count":9,"title":["Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Babai, L., Luks, E.M.: Canonical labeling of graphs. In: STOC 1983, pp. 171\u2013183 (1983)","DOI":"10.1145\/800061.808746"},{"issue":"3","key":"7_CR2","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1006\/jagm.1996.0058","volume":"21","author":"L. Babel","year":"1996","unstructured":"Babel, L., Ponomarenko, I.N., Tinhofer, G.: The isomorphism problem for directed path graphs and for rooted directed path graphs. Journal of Algorithms\u00a021(3), 542\u2013564 (1996)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"7_CR3","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0021-9800(70)80019-9","volume":"9","author":"L.W. Beineke","year":"1970","unstructured":"Beineke, L.W.: Characterizations of derived graphs. Journal of Combinatorial Theory, Series B\u00a09(2), 129\u2013135 (1970)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"7_CR4","unstructured":"Booth, K.S., Colbourn, C.J.: Problems polynomially equivalent to graph isomorphism. Technical Report CS-77-04, Comp. Sci. Dep., Univ. Waterloo (1979)"},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R.B. Boppana","year":"1987","unstructured":"Boppana, R.B., Hastad, J., Zachos, S.: Does co-NP have short interactive proofs? Information Processing Letters\u00a025, 127\u2013132 (1987)","journal-title":"Information Processing Letters"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s00224-004-1154-6","volume":"38","author":"A. Brandst\u00e4dt","year":"2005","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Le, H., Mosca, R.: New graph classes of bounded clique-width. Theory of Computing Systems\u00a038, 623\u2013645 (2005)","journal-title":"Theory of Computing Systems"},{"issue":"3","key":"7_CR7","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D.G. Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Stewart Burlingham, L.: Complement reducible graphs. Discrete Applied Mathematics\u00a03(3), 163\u2013174 (1981)","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR8","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"},{"issue":"3","key":"7_CR9","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/S0097539793260726","volume":"24","author":"W.L. Hsu","year":"1995","unstructured":"Hsu, W.L.: O(m\u00b7n) algorithms for the recognition and isomorphism problems on circular-arc graphs. SIAM Journal on Computing\u00a024(3), 411\u2013439 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR10","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 (1993)"},{"key":"7_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/3-540-45477-2_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Kr\u00e1l","year":"2001","unstructured":"Kr\u00e1l, D., Kratochv\u00edl, J., Tuza, Z., Woeginger, G.J.: Complexity of Coloring Graphs without Forbidden Induced Subgraphs. In: Brandst\u00e4dt, A., Van Le, B. (eds.) WG 2001. LNCS, vol.\u00a02204, pp. 254\u2013262. Springer, Heidelberg (2001)"},{"key":"7_CR12","unstructured":"Kratsch, S., Schweitzer, P.: Full version of paper. arXiv:1208.0142 [cs.DS]"},{"key":"7_CR13","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.\u00a06139, pp. 81\u201392. Springer, Heidelberg (2010)"},{"issue":"44\u201346","key":"7_CR14","doi-asserted-by":"publisher","first-page":"4023","DOI":"10.1016\/j.tcs.2010.08.027","volume":"411","author":"V.V. Lozin","year":"2010","unstructured":"Lozin, V.V.: A decidability result for the dominating set problem. Theoretical Computer Science\u00a0411(44\u201346), 4023\u20134027 (2010)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"7_CR15","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. Journal of the ACM\u00a026(2), 183\u2013195 (1979)","journal-title":"Journal of the ACM"},{"issue":"1","key":"7_CR16","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"E.M. Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences\u00a025(1), 42\u201365 (1982)","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/s11390-009-9242-3","volume":"24","author":"S. Nakano","year":"2009","unstructured":"Nakano, S., Uehara, R., Uno, T.: A new approach to graph recognition and applications to distance-hereditary graphs. Journal of Computer Science and Technology\u00a024, 517\u2013533 (2009)","journal-title":"Journal of Computer Science and Technology"},{"issue":"2","key":"7_CR18","doi-asserted-by":"publisher","first-page":"1621","DOI":"10.1007\/BF01098279","volume":"55","author":"I.N. Ponomarenko","year":"1991","unstructured":"Ponomarenko, I.N.: The isomorphism problem for classes of graphs closed under contraction. Journal of Mathematical Sciences\u00a055(2), 1621\u20131643 (1991)","journal-title":"Journal of Mathematical Sciences"},{"issue":"1","key":"7_CR19","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1112\/plms\/s2-30.1.264","volume":"s2-30","author":"F.P. Ramsey","year":"1930","unstructured":"Ramsey, F.P.: On a problem of formal logic. Proceedings of the London Mathematical Society\u00a0s2-30(1), 264\u2013286 (1930)","journal-title":"Proceedings of the London Mathematical Society"},{"key":"7_CR20","unstructured":"Rao, M.: Decomposition of (gem,co-gem)-free graphs (unpublished), \n                    \n                      http:\/\/www.labri.fr\/perso\/rao\/publi\/decompgemcogem.ps"},{"issue":"3","key":"7_CR21","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. Journal of Computer and System Sciences\u00a037(3), 312\u2013323 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR22","unstructured":"Schweitzer, P.: Problems of unknown complexity: Graph isomorphism and Ramsey theoretic numbers. PhD thesis, Universit\u00e4t des Saarlandes, Germany (2009)"},{"issue":"3","key":"7_CR23","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1016\/j.dam.2004.06.008","volume":"145","author":"R. Uehara","year":"2005","unstructured":"Uehara, R., Toda, S., Nagoya, T.: Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs. Discrete Applied Mathematics\u00a0145(3), 479\u2013482 (2005)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"7_CR24","doi-asserted-by":"publisher","first-page":"150","DOI":"10.2307\/2371086","volume":"54","author":"H. Whitney","year":"1932","unstructured":"Whitney, H.: Congruent graphs and the connectivity of graphs. American Journal of Mathematics\u00a054(1), 150\u2013168 (1932)","journal-title":"American Journal of Mathematics"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34611-8_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T09:00:51Z","timestamp":1620118851000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34611-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642346101","9783642346118"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34611-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}