{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:48:55Z","timestamp":1725889735790},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642332920"},{"type":"electronic","value":"9783642332937"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33293-7_21","type":"book-chapter","created":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T10:50:58Z","timestamp":1346237458000},"page":"218-230","source":"Crossref","is-referenced-by-count":10,"title":["On Tractable Parameterizations of Graph Isomorphism"],"prefix":"10.1007","author":[{"given":"Adam","family":"Bouland","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anuj","family":"Dawar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eryk","family":"Kopczy\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","unstructured":"Arvind, V., Das, B., Johannes, K., Toda, S.: Colored Hypergraph Isomorphism is Fixed Parameter Tractable. In: ECCC 93 (2009)"},{"key":"21_CR2","unstructured":"Babai, L.: Monte-Carlo algorithms in graph isomorphism testing. Tech. Rep. DMS 79-10, Universit\u00e9 de Montr\u00e9al, pp. 1\u201333 (1979)"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"H. Bodlaender","year":"1995","unstructured":"Bodlaender, H., Hafsteinsson, H., Gilbert, J.R., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms\u00a018, 238\u2013255 (1995)","journal-title":"J. Algorithms"},{"issue":"4","key":"21_CR4","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 lsomorphism Chromatic Index on Partial k-Trees. Journal of Algorithms\u00a011(4), 631\u2013643 (1990)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"21_CR5","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"},{"issue":"5","key":"21_CR6","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1016\/j.ejc.2011.09.014","volume":"33","author":"Z. Dvo\u0159\u00e1k","year":"2012","unstructured":"Dvo\u0159\u00e1k, Z., Giannopoulou, A., Thilikos, D.M.: Forbidden graphs for tree-depth. European Journal of Combinatorics\u00a033(5), 969\u2013979 (2012)","journal-title":"European Journal of Combinatorics"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Grohe, M.: Where First-Order and Monadic Second-Order Logic Coincide. Arxiv preprint arXiv:1204.6291, pp. 1\u201315 (2012)","DOI":"10.1109\/LICS.2012.37"},{"issue":"3","key":"21_CR8","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s004930050059","volume":"19","author":"S. Evdokimov","year":"1999","unstructured":"Evdokimov, S., Ponomarenko, I.: Isomorphism of Coloured Graphs with Slowly Increasing Multiplicity of Jordan Blocks. Combinatorica\u00a019(3), 321\u2013333 (1999)","journal-title":"Combinatorica"},{"issue":"4","key":"21_CR9","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1007\/s00224-009-9167-9","volume":"45","author":"M. Fellows","year":"2009","unstructured":"Fellows, M., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F., Saurabh, S.: The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number. Theory of Computing Systems\u00a045(4), 822\u2013848 (2009)","journal-title":"Theory of Computing Systems"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Furst, M., Hopcroft, J.: Luks: Polynomial-time algorithms for permutation groups. In: Proc. FOCS 1980, pp. 36\u201341 (1980)","DOI":"10.1109\/SFCS.1980.34"},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-642-11269-0_15","volume-title":"Parameterized and Exact Computation","author":"R. Ganian","year":"2009","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Kneis, J., Langer, A., Obdr\u017e\u00e1lek, J., Rossmanith, P.: On Digraph Width Measures in Parameterized Algorithmics. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 185\u2013197. Springer, Heidelberg (2009)"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Giannopoulou, A., Hunter, P., Thilikos, D.: LIFO-search: A min-max theorem and a searching game for cycle-rank and tree-depth. Submitted to J. Discrete Math. (2011)","DOI":"10.1016\/j.endm.2011.09.064"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Grohe, M., Marx, D.: Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs. In: Proc. STOC 2012, pp. 173\u2013192 (2012)","DOI":"10.1145\/2213977.2213996"},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Fixed-point definability and polynomial time on graphs with excluded minors. In: Proc. LICS 2010, pp. 179\u2013188 (2010)","DOI":"10.1109\/LICS.2010.22"},{"issue":"3","key":"21_CR15","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1137\/1033099","volume":"33","author":"M. Heath","year":"1991","unstructured":"Heath, M., Ng, E., Peyton, B.: Parallel algorithms for sparse linear systems. SIAM Review\u00a033(3), 420\u2013460 (1991)","journal-title":"SIAM Review"},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/0404010","volume":"4","author":"D. Kleitman","year":"1991","unstructured":"Kleitman, D., West, D.: Spanning Trees with Many Leaves. SIAM J. Discrete Math.\u00a04, 99\u2013106 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"21_CR17","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":"21_CR18","doi-asserted-by":"crossref","unstructured":"Lindell, S.: A logspace algorithm for tree canonization. In: Proc. STOC 1992, pp. 400\u2013404 (1992)","DOI":"10.1145\/129712.129750"},{"issue":"1","key":"21_CR19","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1090\/S0273-0979-05-01088-8","volume":"43","author":"L. Lov\u00e1sz","year":"2006","unstructured":"Lov\u00e1sz, L.: Graph minor theory. Bulletin of the AMS\u00a043(1), 75\u201386 (2006)","journal-title":"Bulletin of the AMS"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Luks, E.: Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences (1982)","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"21_CR21","unstructured":"Manne, F.: An Algorithm for Computing an Elimination Tree of Minimum Height for a Tree. Tech. Rep. CS-91-59, University of Bergen, Norway (1992)"},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"Miller, G.: Isomorphism testing for graphs of bounded genus. In: Proc. STOC 1980, pp. 225\u2013235 (1980)","DOI":"10.1145\/800141.804670"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity: Graphs, Structures and Algorithms. Algorithms and Combinatorics, vol.\u00a028. Springer (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"issue":"6","key":"21_CR24","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J. Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Tree-depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics\u00a027(6), 1022\u20131041 (2006)","journal-title":"European Journal of Combinatorics"},{"key":"21_CR25","first-page":"147","volume":"174","author":"I. Ponomarenko","year":"1988","unstructured":"Ponomarenko, I.: The isomorphism problem for classes of graphs that are invariant with respect to contraction. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov (LOMI)\u00a0174, 147\u2013177 (1988) (Russian)","journal-title":"Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI)"},{"key":"21_CR26","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.: Graph minors XX. Wagners conjecture. Journal of Combinatorial Theory, Series B\u00a092, 325\u2013357 (2004)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"8","key":"21_CR27","doi-asserted-by":"publisher","first-page":"2388","DOI":"10.1093\/ietisy\/e89-d.8.2388","volume":"E89-D","author":"S. Toda","year":"2006","unstructured":"Toda, S.: Computing automorphism groups of chordal graphs whose simplicial components are of small size. IEICE Transactions on Information and Systems\u00a0E89-D(8), 2388\u20132401 (2006)","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"2","key":"21_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","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33293-7_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:03:26Z","timestamp":1620129806000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33293-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642332920","9783642332937"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33293-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}