{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:04Z","timestamp":1781077684902,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642392054","type":"print"},{"value":"9783642392061","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_17","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"196-207","source":"Crossref","is-referenced-by-count":20,"title":["Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marek","family":"Cygan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Aigner, M., Ziegler, G.: Proofs from the book, Berlin, Germany (2010)","DOI":"10.1007\/978-3-642-00856-6"},{"issue":"4","key":"17_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected Hamiltonicity. In: FOCS, pp. 173\u2013182 (2010)","DOI":"10.1109\/FOCS.2010.24"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Taslaman, N.: Shortest cycle through specified elements. In: Rabani, Y. (ed.) SODA, pp. 1747\u20131753. SIAM (2012)","DOI":"10.1137\/1.9781611973099.139"},{"key":"17_CR5","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time. CoRR, abs\/1211.1505 (2012)"},{"key":"17_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-13731-0_10","volume-title":"Algorithm Theory - SWAT 2010","author":"Y. Cao","year":"2010","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 93\u2013104. Springer, Heidelberg (2010)"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Kratsch, S., Nederlof, J.: Fast Hamiltonicity checking via bases of perfect matchings (2012) (to appear at STOC 2013)","DOI":"10.1145\/2488608.2488646"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: FOCS, pp. 150\u2013159 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"issue":"5","key":"17_CR9","doi-asserted-by":"publisher","first-page":"1606","DOI":"10.1016\/j.jcss.2012.02.004","volume":"78","author":"F. Dorn","year":"2012","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Catalan structures and dynamic programming in H-minor-free graphs. J. Comput. Syst. Sci.\u00a078(5), 1606\u20131622 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"17_CR10","doi-asserted-by":"publisher","first-page":"61","DOI":"10.7155\/jgaa.00137","volume":"11","author":"D. Eppstein","year":"2007","unstructured":"Eppstein, D.: The traveling salesman problem for cubic graphs. J. Graph Algorithms Appl.\u00a011(1), 61\u201381 (2007)","journal-title":"J. Graph Algorithms Appl."},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs. In: PODC, pp. 159\u2013168 (2011)","DOI":"10.1145\/1993806.1993829"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. (2001)","DOI":"10.1145\/568438.568455"},{"issue":"4","key":"17_CR13","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci.\u00a063(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR14","unstructured":"Kleinberg, J., Tardos, \u00c9.: Algorithm Design (2005)"},{"key":"17_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/978-3-540-70575-8_47","volume-title":"Automata, Languages and Programming","author":"I. Koutis","year":"2008","unstructured":"Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 575\u2013586. Springer, Heidelberg (2008)"},{"key":"17_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/978-3-642-02927-1_54","volume-title":"Automata, Languages and Programming","author":"I. Koutis","year":"2009","unstructured":"Koutis, I., Williams, R.: Limits and applications of group algebras for parameterized problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 653\u2013664. Springer, Heidelberg (2009)"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In: SODA, pp. 777\u2013789 (2011)","DOI":"10.1137\/1.9781611973082.61"},{"key":"17_CR18","unstructured":"Lov\u00e1sz, L.: On determinants, matchings, and random algorithms. In: FCT, pp. 565\u2013574 (1979)"},{"issue":"1","key":"17_CR19","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica\u00a07(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"key":"17_CR20","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms (2002)"},{"issue":"4","key":"17_CR21","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/BF01192528","volume":"15","author":"R. Raz","year":"1995","unstructured":"Raz, R., Spieker, B.: On the \u201dlog rank\u201d-conjecture in communication complexity. Combinatorica\u00a015(4), 567\u2013588 (1995)","journal-title":"Combinatorica"},{"issue":"1","key":"17_CR22","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory\u00a036(1), 49\u201364 (1984)","journal-title":"J. Comb. Theory"},{"issue":"6","key":"17_CR23","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R. Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length k in \n                    \n                      \n                    \n                    $\\mathcal{O}^\\star(2^{k}$\n                  ) time. Inf. Process. Lett.\u00a0109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."},{"key":"17_CR24","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than coppersmith-winograd. In: STOC, pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:33:25Z","timestamp":1557912805000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}