{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:06Z","timestamp":1781077686998,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,6]]},"DOI":"10.1145\/2488608.2488646","type":"proceedings-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T16:35:41Z","timestamp":1369758941000},"page":"301-310","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Fast hamiltonicity checking via bases of perfect matchings"],"prefix":"10.1145","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Kratsch","sequence":"additional","affiliation":[{"name":"Technical University Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[{"name":"Utrecht University, Utrecht, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational complexity: a modern approach","author":"Arora S.","year":"2009","unstructured":"S. Arora and B. Barak . Computational complexity: a modern approach . 2009 . S. Arora and B. Barak. Computational complexity: a modern approach. 2009."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90033-6"},{"key":"e_1_3_2_1_4_1","volume-title":"Combinatorial processes and dynamic programming","author":"Bellman R.","year":"1958","unstructured":"R. Bellman . Combinatorial processes and dynamic programming . 1958 . R. Bellman. Combinatorial processes and dynamic programming. 1958."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321111"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.24"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9185-7"},{"key":"e_1_3_2_1_8_1","first-page":"11","volume-title":"SIROCCO","volume":"4474","author":"Bodlaender H.","year":"2007","unstructured":"H. Bodlaender . Treewidth : Structure and algorithms . In SIROCCO , volume 4474 , pages 11 -- 25 . 2007 . H. Bodlaender. Treewidth: Structure and algorithms. In SIROCCO, volume 4474, pages 11--25. 2007."},{"key":"e_1_3_2_1_9_1","volume-title":"Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time. CoRR, abs\/1211.1505","author":"Bodlaender H. L.","year":"2012","unstructured":"H. L. Bodlaender , M. Cygan , S. Kratsch , and J. Nederlof . Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time. CoRR, abs\/1211.1505 , 2012 . H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof. Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time. CoRR, abs\/1211.1505, 2012."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11409-0_4"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.36"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.02.004"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00137"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9133-3"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"Fomin F. V.","year":"2010","unstructured":"F. V. Fomin and D. Kratsch . Exact Exponential Algorithms . Springer-Verlag New York, Inc. , New York, NY, USA , 1 st edition, 2010 . F. V. Fomin and D. Kratsch. Exact Exponential Algorithms. Springer-Verlag New York, Inc., New York, NY, USA, 1st edition, 2010.","edition":"1"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972986.8"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993829"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/800029.808532"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_24_1","first-page":"108","volume-title":"COCOON","author":"Iwama K.","year":"2007","unstructured":"K. Iwama and T. Nakashima . An improved exact algorithm for cubic graph TSP . In COCOON , pages 108 -- 117 , 2007 . K. Iwama and T. Nakashima. An improved exact algorithm for cubic graph TSP. In COCOON, pages 108--117, 2007."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90044-X"},{"key":"e_1_3_2_1_26_1","volume-title":"Algorithm Design","author":"Kleinberg J.","year":"2005","unstructured":"J. Kleinberg and \u00c9. Tardos. Algorithm Design . 2005 . J. Kleinberg and \u00c9. Tardos. Algorithm Design. 2005."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800179.810218"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133097"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_3_2_1_31_1","unstructured":"R. Niedermeier. Invitation to Fixed-Parameter Algorithms. 2002.  R. Niedermeier. Invitation to Fixed-Parameter Algorithms. 2002."},{"key":"e_1_3_2_1_32_1","first-page":"1065","volume-title":"SODA","author":"Patrascu M.","year":"2010","unstructured":"M. Patrascu and R. Williams . On the possibility of faster sat algorithms . In SODA , pages 1065 -- 1075 , 2010 . M. Patrascu and R. Williams. On the possibility of faster sat algorithms. In SODA, pages 1065--1075, 2010."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192528"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_3_2_1_35_1","first-page":"185","volume-title":"Combinatorial Optimization","author":"Woeginger G. J.","year":"2001","unstructured":"G. J. Woeginger . Exact algorithms for NP-hard problems: A survey . In Combinatorial Optimization , pages 185 -- 208 , 2001 . G. J. Woeginger. Exact algorithms for NP-hard problems: A survey. In Combinatorial Optimization, pages 185--208, 2001."}],"event":{"name":"STOC'13: Symposium on Theory of Computing","location":"Palo Alto California USA","acronym":"STOC'13","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fifth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488646","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2488608.2488646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:20Z","timestamp":1750235960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488646"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":34,"alternative-id":["10.1145\/2488608.2488646","10.1145\/2488608"],"URL":"https:\/\/doi.org\/10.1145\/2488608.2488646","relation":{},"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}