{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:50:07Z","timestamp":1767340207265,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,3,9]],"date-time":"2017-03-09T00:00:00Z","timestamp":1489017600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,3,9]],"date-time":"2017-03-09T00:00:00Z","timestamp":1489017600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF-0964655"],"award-info":[{"award-number":["CCF-0964655"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF-1320814"],"award-info":[{"award-number":["CCF-1320814"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s00224-017-9751-3","type":"journal-article","created":{"date-parts":[[2017,3,9]],"date-time":"2017-03-09T02:13:51Z","timestamp":1489025631000},"page":"283-304","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Space Saving by Dynamic Algebraization Based on Tree-Depth"],"prefix":"10.1007","volume":"61","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5354-3226","authenticated-orcid":false,"given":"Martin","family":"F\u00fcrer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huiwen","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,9]]},"reference":[{"key":"9751_CR1","first-page":"7","volume-title":"Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence","author":"E Amir","year":"2001","unstructured":"Amir, E.: Efficient Approximation for Triangulation of Minimum Treewidth Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, pp 7\u201315 (2001)"},{"issue":"4","key":"9751_CR2","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/s00453-008-9180-4","volume":"56","author":"E Amir","year":"2010","unstructured":"Amir, E.: Approximation algorithms for treewidth. Algorithmica 56(4), 448\u2013479 (2010). doi:\n                    10.1007\/s00453-008-9180-4","journal-title":"Algorithmica"},{"key":"9751_CR3","doi-asserted-by":"publisher","first-page":"914","DOI":"10.1137\/1.9781611973099.73","volume-title":"23Rd Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A Bj\u00f6rklund","year":"2012","unstructured":"Bj\u00f6rklund, A.: Counting Perfect Matchings as Fast as Ryser 23Rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp 914\u2013921 (2012)"},{"issue":"2","key":"9751_CR4","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/s00453-007-9149-8","volume":"52","author":"A Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Exact algorithms for exact satisfiability and number of perfect matchings. Algorithmica 52(2), 226\u2013249 (2008)","journal-title":"Algorithmica"},{"key":"9751_CR5","first-page":"67","volume-title":"39Th Annual ACM Symposium on Theory of Computing","author":"A Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier Meets M\u00f6bius: Fast Subset Convolution 39Th Annual ACM Symposium on Theory of Computing, pp 67\u201374 (2007)"},{"key":"9751_CR6","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/3-540-19488-6_110","volume-title":"15Th International Colloquium on Automata, Languages and Programming","author":"HL Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Dynamic Programming on Graphs with Bounded Treewidth 15Th International Colloquium on Automata, Languages and Programming, pp 105\u2013118 (1988)"},{"key":"9751_CR7","first-page":"1","volume-title":"14Th International Workshop on Graph-Theoretic Concepts in Computer Science","author":"HL Bodlaender","year":"1989","unstructured":"Bodlaender, H.L.: NC-Algorithms for Graphs with Small Treewidth 14Th International Workshop on Graph-Theoretic Concepts in Computer Science, pp 1\u201310 (1989)"},{"key":"9751_CR8","first-page":"226","volume-title":"25Th Annual ACM Symposium on Theory of Computing","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A Linear Time Algorithm for Finding Tree-Decompositions of Small Treewidth 25Th Annual ACM Symposium on Theory of Computing, pp 226\u2013234 (1993)"},{"key":"9751_CR9","first-page":"1","volume-title":"31St Conference on Current Trends in Theory and Practice of Computer Science","author":"HL Bodlaender","year":"2005","unstructured":"Bodlaender, H.L.: Discovering Treewidth 31St Conference on Current Trends in Theory and Practice of Computer Science, pp 1\u201316 (2005)"},{"key":"9751_CR10","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1109\/FOCS.2013.60","volume-title":"54Th Annual IEEE Symposium on Foundations of Computer Science","author":"HL Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: An O(C\n                           \n                    k\n                  \n                           N) 5-Approximation Algorithm for Treewidth 54Th Annual IEEE Symposium on Foundations of Computer Science, pp 499\u2013508 (2013)"},{"key":"9751_CR11","first-page":"1","volume-title":"17Th International Workshop on Graph-Theoretic Concepts in Computer Science","author":"HL Bodlaender","year":"1992","unstructured":"Bodlaender, H.L., Gilbert, J.R., Kloks, T., Hafsteinsson, H.: Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height 17Th International Workshop on Graph-Theoretic Concepts in Computer Science, pp 1\u201312 (1992)"},{"issue":"2-3","key":"9751_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0166-218X(03)00440-2","volume":"136","author":"V Bouchitt\u00e9","year":"2004","unstructured":"Bouchitt\u00e9, V., Kratsch, D., M\u00fcller, H., Todinca, I.: On treewidth approximations. Discrete Appl. Math. 136(2-3), 183\u2013196 (2004)","journal-title":"Discrete Appl. Math."},{"key":"9751_CR13","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 52nd Annual IEEE Symposium on Foundations of Computer Science, pp 150\u2013159 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"issue":"2","key":"9751_CR14","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/05064299X","volume":"38","author":"U Feige","year":"2008","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38(2), 629\u2013657 (2008). doi:\n                    10.1137\/05064299X","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9751_CR15","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181\u2013207 (2009)","journal-title":"Algorithmica"},{"issue":"3","key":"9751_CR16","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1137\/070711761","volume":"39","author":"M F\u00fcrer","year":"2009","unstructured":"F\u00fcrer, M.: Faster integer multiplication. SIAM J. Comput. 39(3), 979\u20131005 (2009)","journal-title":"SIAM J. Comput."},{"key":"9751_CR17","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree Decompositions: a Survey Mathematical Foundations of Computer Science, pp 37\u201357 (2001)","DOI":"10.1007\/3-540-44683-4_5"},{"key":"9751_CR18","doi-asserted-by":"publisher","unstructured":"Kenyon, C., Randall, D., Sinclair, A.: Approximating the number of monomer-dimer coverings of a lattice. J. Stat. Phys. 83(3), 637\u2013659 (1996). doi:\n                    10.1007\/BF02183743","DOI":"10.1007\/BF02183743"},{"key":"9751_CR19","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth, Computations and Approximations, vol. 842. Springer (1994)","DOI":"10.1007\/BFb0045375"},{"issue":"1","key":"9751_CR20","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1137\/080715482","volume":"23","author":"J Kneis","year":"2009","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: A bound on the pathwidth of sparse graphs with applications to exact algorithms. SIAM J. Discret. Math. 23(1), 407\u2013427 (2009)","journal-title":"SIAM J. Discret. Math."},{"key":"9751_CR21","doi-asserted-by":"crossref","unstructured":"Koutis, I.: Faster Algebraic Algorithms for Path and Packing Problems 35Th International Colloquium on Automata, Languages and Programming, pp 575\u2013586 (2008)","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"9751_CR22","doi-asserted-by":"crossref","unstructured":"Koutis, I., Williams, R.: Limits and Applications of Group Algebras for Parameterized Problems 36Th International Colloquium on Automata, Languages and Programming, pp 653\u2013664 (2009)","DOI":"10.1007\/978-3-642-02927-1_54"},{"key":"9751_CR23","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Mnich, M., Saurabh, S.: Planar K-Path in Subexponential Time and Polynomial Space 37Th International Workshop on Graph-Theoretic Concepts in Computer Science, pp 262\u2013270 (2011)","DOI":"10.1007\/978-3-642-25870-1_24"},{"key":"9751_CR24","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Nederlof, J.: Saving Space by Algebraization. In: 42nd ACM Symposium on Theory of Computing, pp 321\u2013330 (2010)","DOI":"10.1145\/1806689.1806735"},{"issue":"1","key":"9751_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"GL Miller","year":"1997","unstructured":"Miller, G.L., Teng, S.H., Thurston, W., Vavasis, S.A.: Separators for sphere-packings and nearest neighbor graphs. J. ACM 44(1), 1\u201329 (1997)","journal-title":"J. ACM"},{"issue":"4","key":"9751_CR26","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1007\/s00453-012-9630-x","volume":"65","author":"J Nederlof","year":"2013","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica 65(4), 868\u2013884 (2013)","journal-title":"Algorithmica"},{"key":"9751_CR27","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb. 27(6), 1022\u20131041 (2006)"},{"key":"9751_CR28","doi-asserted-by":"crossref","unstructured":"van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution 17Th Annual European Symposium on Algorithms, pp 566\u2013577 (2009)","DOI":"10.1007\/978-3-642-04128-0_51"},{"key":"9751_CR29","doi-asserted-by":"crossref","unstructured":"van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion\/Exclusion Meets Measure and Conquer 17Th Annual European Symposium on Algorithms, pp 554\u2013565 (2009)","DOI":"10.1007\/978-3-642-04128-0_50"},{"issue":"4","key":"9751_CR30","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/BF00531932","volume":"2","author":"GC Rota","year":"1964","unstructured":"Rota, G.C.: On the foundations of combinatorial theory. i. theory of m\u00f6bius functions. Zeitschrift f\u00fc,r Wahrscheinlichkeitstheorie und Verwandte Gebiete 2(4), 340\u2013368 (1964)","journal-title":"Zeitschrift f\u00fc,r Wahrscheinlichkeitstheorie und Verwandte Gebiete"},{"key":"9751_CR31","doi-asserted-by":"crossref","unstructured":"Stanley, R., Rota, G.: Enumerative Combinatorics, vol. 1. Cambridge University Press (2000)","DOI":"10.1017\/CBO9781139058520.002"},{"key":"9751_CR32","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1080\/14786436108243366","volume":"6","author":"H Temperley","year":"1961","unstructured":"Temperley, H., Fisher, M.: Dimer problem in statistical mechanics - an exact result. Philos. Mag. 6, 1061\u20131063 (1961)","journal-title":"Philos. Mag."},{"key":"9751_CR33","doi-asserted-by":"crossref","unstructured":"Woeginger, G.J.: Space and Time Complexity of Exact Algorithms: Some Open Problems (Invited Talk) 1St International Workshop on Parameterized and Exact Computation, pp 281\u2013290 (2004)","DOI":"10.1007\/978-3-540-28639-4_25"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9751-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9751-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9751-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T05:36:58Z","timestamp":1589693818000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9751-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,9]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["9751"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9751-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,3,9]]},"assertion":[{"value":"9 March 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}