{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:46:34Z","timestamp":1725558394571},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642137303"},{"type":"electronic","value":"9783642137310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13731-0_9","type":"book-chapter","created":{"date-parts":[[2010,6,10]],"date-time":"2010-06-10T11:00:50Z","timestamp":1276167650000},"page":"81-92","source":"Crossref","is-referenced-by-count":18,"title":["Isomorphism for Graphs of Bounded Feedback Vertex Set Number"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","unstructured":"Arvind, V., Das, B., K\u00f6bler, J., Toda, S.: Colored hypergraph isomorphism is fixed parameter tractable. ECCC 16(093) (2009)"},{"key":"9_CR2","first-page":"34","volume-title":"FCT","author":"L. Babai","year":"1981","unstructured":"Babai, L.: Moderately exponential bound for graph isomorphism. In: FCT, pp. 34\u201350. Springer, Heidelberg (1981)"},{"key":"9_CR3","first-page":"310","volume-title":"STOC","author":"L. Babai","year":"1982","unstructured":"Babai, L., Grigoryev, D.Y., Mount, D.M.: Isomorphism of graphs with bounded eigenvalue multiplicity. In: STOC, pp. 310\u2013324. ACM, New York (1982)"},{"key":"9_CR4","first-page":"171","volume-title":"STOC","author":"L. Babai","year":"1983","unstructured":"Babai, L., Luks, E.M.: Canonical labeling of graphs. In: STOC, pp. 171\u2013183. ACM, New York (1983)"},{"issue":"4","key":"9_CR5","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"H.L. Bodlaender","year":"1990","unstructured":"Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. Journal of Algorithms\u00a011(4), 631\u2013643 (1990)","journal-title":"Journal of Algorithms"},{"issue":"6","key":"9_CR6","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"9_CR7","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters\u00a058(4), 171\u2013176 (1996)","journal-title":"Information Processing Letters"},{"issue":"7","key":"9_CR8","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J. Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. Journal of Computer and System Sciences\u00a074(7), 1188\u20131198 (2008)","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR9","volume-title":"Parameterized Complexity (Monographs in Computer Science)","author":"R.G. Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity (Monographs in Computer Science). Springer, Heidelberg (1998)"},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1007\/978-3-642-11269-0_10","volume-title":"IWPEC 2009","author":"R. Enciso","year":"2009","unstructured":"Enciso, R., Fellows, M.R., Guo, J., Kanj, I.A., Rosamond, F.A., Such\u00fd, O.: What makes equitable connected partition easy. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 122\u2013133. Springer, Heidelberg (2009)"},{"issue":"3","key":"9_CR11","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s004930050059","volume":"19","author":"S. Evdokimov","year":"1999","unstructured":"Evdokimov, S., Ponomarenko, I.N.: Isomorphism of coloured graphs with slowly increasing multiplicity of jordan blocks. Combinatorica\u00a019(3), 321\u2013333 (1999)","journal-title":"Combinatorica"},{"key":"9_CR12","first-page":"236","volume-title":"STOC","author":"I.S. Filotti","year":"1980","unstructured":"Filotti, I.S., Mayer, J.N.: A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. In: STOC, pp. 236\u2013243. ACM, New York (1980)"},{"key":"9_CR13","first-page":"36","volume-title":"FOCS","author":"M.L. Furst","year":"1980","unstructured":"Furst, M.L., Hopcroft, J.E., Luks, E.M.: Polynomial-time algorithms for permutation groups. In: FOCS, pp. 36\u201341. IEEE, Los Alamitos (1980)"},{"key":"9_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.\u00a0H. Freeman, New York (1979)"},{"key":"9_CR15","first-page":"310","volume-title":"STOC","author":"J.E. Hopcroft","year":"1974","unstructured":"Hopcroft, J.E., Wong, J.K.: Linear time algorithm for isomorphism of planar graphs. In: STOC, pp. 310\u2013324. ACM, New York (1974)"},{"key":"9_CR16","first-page":"771","volume-title":"FOCS","author":"K. Kawarabayashi","year":"2008","unstructured":"Kawarabayashi, K., Mohar, B., Reed, B.A.: A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In: FOCS, pp. 771\u2013780. IEEE, Los Alamitos (2008)"},{"issue":"2","key":"9_CR17","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM Journal on Computing\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"9_CR18","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":"9_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/11917496_4","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 37\u201348. Springer, Heidelberg (2006)"},{"key":"9_CR20","first-page":"225","volume-title":"STOC","author":"G.L. Miller","year":"1980","unstructured":"Miller, G.L.: Isomorphism testing for graphs of bounded genus. In: STOC, pp. 225\u2013235. ACM, New York (1980)"},{"issue":"2","key":"9_CR21","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":"3","key":"9_CR22","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/1159892.1159898","volume":"2","author":"V. Raman","year":"2006","unstructured":"Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Transactions on Algorithms\u00a02(3), 403\u2013415 (2006)","journal-title":"ACM Transactions on Algorithms"},{"issue":"3","key":"9_CR23","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"},{"issue":"1","key":"9_CR24","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/0020-0190(71)90019-6","volume":"1","author":"R.E. Tarjan","year":"1971","unstructured":"Tarjan, R.E.: A V 2 algorithm for determining isomorphism of planar graphs. Information Processing Letters\u00a01(1), 32\u201334 (1971)","journal-title":"Information Processing Letters"},{"key":"9_CR25","first-page":"115","volume-title":"SODA","author":"S. Thomass\u00e9","year":"2009","unstructured":"Thomass\u00e9, S.: A quadratic kernel for feedback vertex set. In: SODA, pp. 115\u2013119. SIAM, Philadelphia (2009)"},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"Toda, S.: Computing automorphism groups of chordal graphs whose simplicial components are of small size. IEICE Transactions\u00a089-D(8), 2388\u20132401 (2006)","DOI":"10.1093\/ietisy\/e89-d.8.2388"},{"issue":"3","key":"9_CR27","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":"2","key":"9_CR28","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/PL00009273","volume":"24","author":"K. Yamazaki","year":"1999","unstructured":"Yamazaki, K., Bodlaender, H.L., de Fluiter, B., Thilikos, D.M.: Isomorphism for graphs of bounded distance width. Algorithmica\u00a024(2), 105\u2013127 (1999)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13731-0_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:42:27Z","timestamp":1606185747000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13731-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642137303","9783642137310"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13731-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}