{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T15:50:59Z","timestamp":1773762659722,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520076","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"914-923","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor"],"prefix":"10.1145","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of California at Santa Barbara, USA"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"IMSc, India \/ University of Bergen, Norway"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_3_2_1_2_1","volume-title":"Luks","author":"Babai L\u00e1szl\u00f3","year":"1983","unstructured":"L\u00e1szl\u00f3 Babai and Eugene M . Luks . 1983 . Canonical Labeling of Graphs. In STOC. 171\u2013183. L\u00e1szl\u00f3 Babai and Eugene M. Luks. 1983. Canonical Labeling of Graphs. In STOC. 171\u2013183."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90013-5"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032077"},{"key":"e_1_3_2_1_5_1","volume-title":"Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh.","author":"Cygan Marek","year":"2015","unstructured":"Marek Cygan , Fedor V. Fomin , \u0141 ukasz Kowalik , Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015 . Parameterized Algorithms. Springer . Marek Cygan, Fedor V. Fomin, \u0141 ukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3426738"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Marek Cygan Daniel Lokshtanov Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2014. Minimum bisection is fixed parameter tractable. In STOC. 323\u2013332.  Marek Cygan Daniel Lokshtanov Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2014. Minimum bisection is fixed parameter tractable. In STOC. 323\u2013332.","DOI":"10.1145\/2591796.2591852"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/140988553"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.07.001"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132720"},{"key":"e_1_3_2_1_11_1","volume-title":"Mayer","author":"Filotti I. S.","year":"1980","unstructured":"I. S. Filotti and Jack N . Mayer . 1980 . A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus (Working Paper). In STOC. 236\u2013243. I. S. Filotti and Jack N. Mayer. 1980. A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus (Working Paper). In STOC. 236\u2013243."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Martin Grohe Ken-ichi Kawarabayashi D\u00e1niel Marx and Paul Wollan. 2011. Finding topological subgraphs is fixed-parameter tractable. In STOC. 479\u2013488.  Martin Grohe Ken-ichi Kawarabayashi D\u00e1niel Marx and Paul Wollan. 2011. Finding topological subgraphs is fixed-parameter tractable. In STOC. 479\u2013488.","DOI":"10.1145\/1993636.1993700"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Martin Grohe and D\u00e1niel Marx. 2012. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. In STOC. 173\u2013192.  Martin Grohe and D\u00e1niel Marx. 2012. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. In STOC. 173\u2013192.","DOI":"10.1145\/2213977.2213996"},{"key":"e_1_3_2_1_14_1","volume-title":"Recent Advances on the Graph Isomorphism Problem. CoRR, abs\/2011.01366","author":"Grohe Martin","year":"2020","unstructured":"Martin Grohe and Daniel Neuen . 2020. Recent Advances on the Graph Isomorphism Problem. CoRR, abs\/2011.01366 ( 2020 ), arXiv:2011.01366. arxiv:2011.01366 Martin Grohe and Daniel Neuen. 2020. Recent Advances on the Graph Isomorphism Problem. CoRR, abs\/2011.01366 (2020), arXiv:2011.01366. arxiv:2011.01366"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453943"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00018"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382082"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.66"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00064"},{"key":"e_1_3_2_1_20_1","volume-title":"Hopcroft and Robert Endre Tarjan","author":"John","year":"1972","unstructured":"John E. Hopcroft and Robert Endre Tarjan . 1972 . Isomorphism of Planar Graphs. In Complexity of Computer Computations . 131\u2013152. John E. Hopcroft and Robert Endre Tarjan. 1972. Isomorphism of Planar Graphs. In Complexity of Computer Computations. 131\u2013152."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80013-3"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"John E. Hopcroft and J. K. Wong. 1974. Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report). In STOC. 172\u2013184.  John E. Hopcroft and J. K. Wong. 1974. Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report). In STOC. 172\u2013184.","DOI":"10.1145\/800119.803896"},{"key":"e_1_3_2_1_23_1","volume-title":"Graph Isomorphism for Bounded Genus Graphs In Linear Time. CoRR, abs\/1511.02460","year":"2015","unstructured":"Ken-ichi Kawarabayashi. 2015. Graph Isomorphism for Bounded Genus Graphs In Linear Time. CoRR, abs\/1511.02460 ( 2015 ), arxiv:1511.02460. arxiv:1511.02460 Ken-ichi Kawarabayashi. 2015. Graph Isomorphism for Bounded Genus Graphs In Linear Time. CoRR, abs\/1511.02460 (2015), arxiv:1511.02460. arxiv:1511.02460"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Ken-ichi Kawarabayashi and Mikkel Thorup. 2011. The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable. In FOCS. 160\u2013169.  Ken-ichi Kawarabayashi and Mikkel Thorup. 2011. The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable. In FOCS. 160\u2013169.","DOI":"10.1109\/FOCS.2011.53"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00592-7"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/140999980"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.135"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00079"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Gary L. Miller. 1980. Isomorphism Testing for Graphs of Bounded Genus. In STOC. 225\u2013235.  Gary L. Miller. 1980. Isomorphism Testing for Graphs of Bounded Genus. In STOC. 225\u2013235.","DOI":"10.1145\/800141.804670"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.88"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.72"},{"key":"e_1_3_2_1_33_1","unstructured":"Micha\u0142 Pilipczuk Nicole Schirrmacher Sebastian Siebertz Szymon Toru\u0144czyk and Alexander Vigny. 2021. Algorithms and data structures for problems definable in first-order logic with connectivity predicates. Manuscript  Micha\u0142 Pilipczuk Nicole Schirrmacher Sebastian Siebertz Szymon Toru\u0144czyk and Alexander Vigny. 2021. Algorithms and data structures for problems definable in first-order logic with connectivity predicates. Manuscript"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01098279"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/247090.247379"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1966.1082573"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.103"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520076","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:16Z","timestamp":1750188676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":38,"alternative-id":["10.1145\/3519935.3520076","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520076","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}