{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:20Z","timestamp":1759638380993},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319084039"},{"type":"electronic","value":"9783319084046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08404-6_32","type":"book-chapter","created":{"date-parts":[[2014,6,25]],"date-time":"2014-06-25T03:55:08Z","timestamp":1403668508000},"page":"368-379","source":"Crossref","is-referenced-by-count":5,"title":["Reduction Techniques for Graph Isomorphism in the Context of Width Parameters"],"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":"32_CR1","unstructured":"Arvind, V., Das, B., K\u00f6bler, J., Toda, S.: Colored hypergraph isomorphism is fixed parameter tractable. In: FSTTCS, pp. 327\u2013337 (2010)"},{"key":"32_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-642-40450-4_13","volume-title":"Algorithms \u2013 ESA 2013","author":"C. Berkholz","year":"2013","unstructured":"Berkholz, C., Bonsma, P., Grohe, M.: Tight lower and upper bounds for the complexity of canonical colour refinement. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol.\u00a08125, pp. 145\u2013156. Springer, Heidelberg (2013)"},{"issue":"6","key":"32_CR3","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 J. Comput.\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"32_CR4","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1023\/A:1027320705349","volume":"7","author":"H.L. Bodlaender","year":"2003","unstructured":"Bodlaender, H.L.: Necessary edges in k-chordalisations of graphs. J. Comb. Optim.\u00a07(3), 283\u2013290 (2003)","journal-title":"J. Comb. Optim."},{"issue":"1-2","key":"32_CR5","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","volume":"276","author":"V. Bouchitt\u00e9","year":"2002","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comput. Sci.\u00a0276(1-2), 17\u201332 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"32_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-642-33293-7_21","volume-title":"Parameterized and Exact Computation","author":"A. Bouland","year":"2012","unstructured":"Bouland, A., Dawar, A., Kopczy\u0144ski, E.: On tractable parameterizations of graph isomorphism. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol.\u00a07535, pp. 218\u2013230. Springer, Heidelberg (2012)"},{"issue":"4","key":"32_CR7","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J.-Y. Cai","year":"1992","unstructured":"Cai, J.-Y., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica\u00a012(4), 389\u2013410 (1992)","journal-title":"Combinatorica"},{"key":"32_CR8","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"},{"issue":"1-3","key":"32_CR9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0012-365X(94)00337-I","volume":"149","author":"G. Ding","year":"1996","unstructured":"Ding, G., Oporowski, B.: On tree-partitions of graphs. Discrete Math.\u00a0149(1-3), 45\u201358 (1996)","journal-title":"Discrete Math."},{"issue":"3","key":"32_CR10","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":"32_CR11","series-title":"An EATCS Series","volume-title":"Parameterized Complexity Theory (Texts in Theoretical Computer Science)","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory (Texts in Theoretical Computer Science). An EATCS Series. Springer, London (2006)"},{"key":"32_CR12","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Large induced subgraphs via triangulations and cmso. In: SODA, pp. 582\u2013583 (2014)","DOI":"10.1137\/1.9781611973402.44"},{"key":"32_CR13","unstructured":"Fuhlbr\u00fcck, F.: Fixed-parameter tractability of the graph isomorphism and canonization problems. Diploma thesis, Humboldt-Universit\u00e4t zu Berlin (2013)"},{"key":"32_CR14","doi-asserted-by":"crossref","unstructured":"Furst, M.L., Hopcroft, J.E., Luks, E.M.: Polynomial-time algorithms for permutation groups. In: FOCS, pp. 36\u201341 (1980)","DOI":"10.1109\/SFCS.1980.34"},{"key":"32_CR15","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":"32_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-49257-7_6","volume-title":"Database Theory - ICDT\u201999","author":"M. Grohe","year":"1998","unstructured":"Grohe, M.: Definability and descriptive complexity on databases of bounded tree-width. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, pp. 70\u201382. Springer, Heidelberg (1998)"},{"issue":"2","key":"32_CR17","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1137\/0603025","volume":"3","author":"M. Klawe","year":"1982","unstructured":"Klawe, M., Corneil, D., Proskurowski, A.: Isomorphism testing in hookup classes. SIAM Journal on Algebraic Discrete Methods\u00a03(2), 260\u2013274 (1982)","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The graph isomorphism problem: Its structural complexity. Birkh\u00e4user Verlag, Basel (1993)","DOI":"10.1007\/978-1-4612-0333-9"},{"key":"32_CR19","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)"},{"key":"32_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/3-540-45678-3_13","volume-title":"Algorithms and Computation","author":"T. Nagoya","year":"2001","unstructured":"Nagoya, T.: Counting graph isomorphisms among chordal graphs with restricted clique number. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223, pp. 136\u2013147. Springer, Heidelberg (2001)"},{"key":"32_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-3-642-35261-4_48","volume-title":"Algorithms and Computation","author":"Y. Otachi","year":"2012","unstructured":"Otachi, Y.: Isomorphism for graphs of bounded connected-path-distance-width. In: Chao, K.-M., Hsu, T.-S., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol.\u00a07676, pp. 455\u2013464. Springer, Heidelberg (2012)"},{"key":"32_CR22","unstructured":"Otachi, Y., Schweitzer, P.: full version of the paper. arXiv:1403.7238 [cs.DM] (2014)"},{"key":"32_CR23","unstructured":"Schweitzer, P.: Problems of unknown complexity: graph isomorphism and Ramsey theoretic numbers. Phd thesis, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany (July 2009)"},{"key":"32_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/978-3-642-23719-5_32","volume-title":"Algorithms \u2013 ESA 2011","author":"P. Schweitzer","year":"2011","unstructured":"Schweitzer, P.: Isomorphism of (mis)labeled graphs. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 370\u2013381. Springer, Heidelberg (2011)"},{"key":"32_CR25","doi-asserted-by":"crossref","unstructured":"Seese, D.: Tree-partite graphs and the complexity of algorithms. In: Budach, L. (ed.) Fundamentals of Computation Theory, FCT 1985. LNCS, vol.\u00a0199, pp. 412\u2013421. Springer, Heidelberg (1985)","DOI":"10.1007\/BFb0028825"},{"key":"32_CR26","unstructured":"Toda, S.: Gurafu Doukeisei Hantei Mondai (The Graph Isomorphism Decision Problem). Nihon University, Tokyo, Japan (2001) (in Japanese)"},{"key":"32_CR27","doi-asserted-by":"crossref","unstructured":"Toda, S.: Computing automorphism groups of chordal graphs whose simplicial components are of small size. IEICE Transactions 89-D(8), 2388\u20132401 (2006)","DOI":"10.1093\/ietisy\/e89-d.8.2388"},{"issue":"2","key":"32_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 \u2013 SWAT 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08404-6_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T04:11:19Z","timestamp":1558930279000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08404-6_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319084039","9783319084046"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08404-6_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}