{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:48:37Z","timestamp":1725889717789},"publisher-location":"Berlin, Heidelberg","reference-count":26,"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_16","type":"book-chapter","created":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T10:50:58Z","timestamp":1346237458000},"page":"159-170","source":"Crossref","is-referenced-by-count":0,"title":["Fast Monotone Summation over Disjoint Sets"],"prefix":"10.1007","author":[{"given":"Petteri","family":"Kaski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikko","family":"Koivisto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Janne H.","family":"Korhonen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"16_CR1","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N. Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica\u00a017(3), 209\u2013223 (1997)","journal-title":"Algorithmica"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Bellman, R.: Combinatorial processes and dynamic programming. In: Combinatorial Analysis. Proceedings of Symposia in Applied Mathematics, vol.\u00a010, pp. 217\u2013249. ACM (1960)","DOI":"10.1090\/psapm\/010\/0113718"},{"issue":"1","key":"16_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R. Bellman","year":"1962","unstructured":"Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM\u00a09(1), 61\u201363 (1962)","journal-title":"J. ACM"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1109\/FOCS.2010.24","volume-title":"51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)","author":"A. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected Hamiltonicity. In: 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pp. 173\u2013182. IEEE Computer Society, Los Alamitos (2010)"},{"key":"16_CR5","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets m\u00f6bius: fast subset convolution (manuscript submitted for publication)"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/FOCS.2008.40","volume-title":"49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008)","author":"A. Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Computing the Tutte polynomial in vertex-exponential time. In: 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pp. 677\u2013686. IEEE Computer Society, Los Alamitos (2008)"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1007\/978-3-642-04128-0_52","volume-title":"Algorithms - ESA 2009","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Counting Paths and Packings in Halves. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 578\u2013586. Springer, Heidelberg (2009)"},{"issue":"20","key":"16_CR8","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1016\/j.ipl.2010.07.005","volume":"110","author":"A. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Evaluation of permanents in rings and semirings. Information Processing Letters\u00a0110(20), 867\u2013870 (2010)","journal-title":"Information Processing Letters"},{"issue":"2","key":"16_CR9","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM Journal on Computing\u00a039(2), 546\u2013563 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR10","first-page":"663","volume":"12","author":"C.P. Campos de","year":"2011","unstructured":"de Campos, C.P., Ji, Q.: Efficient structure learning of bayesian networks using constraints. Journal of Machine Learning Research\u00a012, 663\u2013689 (2011)","journal-title":"Journal of Machine Learning Research"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1109\/SFCS.2005.39","volume-title":"46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005)","author":"H. Cohn","year":"2005","unstructured":"Cohn, H., Kleinberg, R., Szegedy, B., Umans, C.: Group-theoretic algorithms for matrix multiplication. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 379\u2013388. IEEE Computer Society, Los Alamitos (2005)"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"J.W. Cooley","year":"1965","unstructured":"Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation\u00a019, 297\u2013301 (1965)","journal-title":"Mathematics of Computation"},{"issue":"3","key":"16_CR13","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation\u00a09(3), 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"16_CR14","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 (2011) (manuscript)","DOI":"10.1109\/FOCS.2011.23"},{"key":"16_CR15","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company (1979)"},{"issue":"1","key":"16_CR16","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M. Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics\u00a010(1), 196\u2013210 (1962)","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"issue":"4","key":"16_CR17","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A. Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM Journal on Computing\u00a07(4), 413\u2013423 (1978)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR18","unstructured":"Kerr, L.R.: The effect of algebraic structure on the computational complexity of matrix multiplications. Ph.D. thesis, Cornell University (1970)"},{"key":"16_CR19","series-title":"Seminumerical Algorithms","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming, 3rd edn. Seminumerical Algorithms, vol.\u00a02. Addison\u2013Wesley, Upper Saddle River (1998)","edition":"3"},{"key":"16_CR20","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":"16_CR21","first-page":"321","volume-title":"2010 ACM International Symposium on Theory of Computing (STOC 2010)","author":"D. Lokshtanov","year":"2010","unstructured":"Lokshtanov, D., Nederlof, J.: Saving space by algebraization. In: 2010 ACM International Symposium on Theory of Computing (STOC 2010), pp. 321\u2013330. ACM, New York (2010)"},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1137\/0215037","volume":"15","author":"L.G. Valiant","year":"1986","unstructured":"Valiant, L.G.: Negation is powerless for boolean slice functions. SIAM Journal on Computing\u00a015, 531\u2013535 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR23","first-page":"455","volume-title":"2009 ACM International Symposium on Theory of Computing (STOC 2009)","author":"V. Vassilevska","year":"2009","unstructured":"Vassilevska, V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. In: 2009 ACM International Symposium on Theory of Computing (STOC 2009), pp. 455\u2013464. ACM, New York (2009)"},{"issue":"3","key":"16_CR24","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/1798596.1798597","volume":"6","author":"V. Vassilevska","year":"2010","unstructured":"Vassilevska, V., Williams, R., Yuster, R.: Finding heaviest H-subgraphs in real weighted graphs, with applications. ACM Transactions on Algorithms\u00a06(3), Art. 44, 23 (2010)","journal-title":"ACM Transactions on Algorithms"},{"issue":"6","key":"16_CR25","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 O\n                *(2\n                  k\n                ) time. Information Processing Letters\u00a0109(6), 315\u2013318 (2009)","journal-title":"Information Processing Letters"},{"key":"16_CR26","unstructured":"Yates, F.: The Design and Analysis of Factorial Experiments. Imperial Bureau of Soil Science, Harpenden, England (1937)"}],"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_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:03:23Z","timestamp":1620129803000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33293-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642332920","9783642332937"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33293-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}