{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:02:23Z","timestamp":1772906543252,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642041273","type":"print"},{"value":"9783642041280","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_52","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"578-586","source":"Crossref","is-referenced-by-count":20,"title":["Counting Paths and Packings in Halves"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thore","family":"Husfeldt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petteri","family":"Kaski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikko","family":"Koivisto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"52_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Gutner, S.: Balanced hashing, color coding and approximate counting. Electronic Colloquium on Computational Complexity, Report TR09-12 (2009)","DOI":"10.1007\/978-3-642-11269-0_1"},{"key":"52_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. Assoc. Comput. Mach.\u00a042, 844\u2013856 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"52_CR3","doi-asserted-by":"crossref","unstructured":"Bellman, R.: Combinatorial processes and dynamic programming. In: Bellman, R., Hall Jr., M. (eds.) Combinatorial Analysis. Proceedings of Symposia in Applied Mathematics 10, pp. 217\u2013249. American Mathematical Society (1960)","DOI":"10.1090\/psapm\/010\/0113718"},{"key":"52_CR4","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. Assoc. Comput. Mach.\u00a09, 61\u201363 (1962)","journal-title":"J. Assoc. Comput. Mach."},{"key":"52_CR5","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion\u2013exclusion. SIAM J. Comput. (to appear) Special Issue for FOCS\u00a02006"},{"key":"52_CR6","first-page":"67","volume-title":"39th ACM Symposium on Theory of Computing (STOC\u00a02007)","author":"A. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: 39th ACM Symposium on Theory of Computing (STOC\u00a02007), pp. 67\u201374. ACM Press, New York (2007)"},{"key":"52_CR7","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Trimmed Moebius inversion and graphs of bounded degree. In: 25th International Symposium on Theoretical Aspects of Computer Science (STACS\u00a02008). Dagstuhl Seminar Proceedings 08001, pp. 85\u201396. IBFI Schloss Dagstuhl (2008)"},{"key":"52_CR8","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The fast intersection transform with applications to counting paths. CoRR, abs\/0809.2489 (2008)"},{"key":"52_CR9","unstructured":"Chen, J., Lu, S., Sze, S.-H., Zhang, F.: Improved algorithms for path, matching, and packing problems. In: 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02007), Philadelphia, PA, USA, pp. 298\u2013307. Society for Industrial and Applied Mathematics (2007)"},{"key":"52_CR10","doi-asserted-by":"publisher","DOI":"10.1515\/9781400884179","volume-title":"Linear Programming and Extensions","author":"G. Danzig","year":"1963","unstructured":"Danzig, G.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)"},{"key":"52_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"52_CR12","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J. Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput.\u00a033, 892\u2013922 (2004)","journal-title":"SIAM J. Comput."},{"key":"52_CR13","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1137\/0216034","volume":"16","author":"Y. Gurevich","year":"1987","unstructured":"Gurevich, Y., Shelah, S.: Expected computation time for Hamiltonian path problem. SIAM J. Comput.\u00a016, 486\u2013502 (1987)","journal-title":"SIAM J. Comput."},{"key":"52_CR14","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. J. Soc. Indust. Appl. Math.\u00a010, 196\u2013210 (1962)","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"52_CR15","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E. Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack Problem. J. Assoc. Comput. Mach.\u00a021, 277\u2013292 (1974)","journal-title":"J. Assoc. Comput. Mach."},{"key":"52_CR16","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.jalgor.2003.07.001","volume":"50","author":"W. Jia","year":"2004","unstructured":"Jia, W., Zhang, C., Chen, J.: An efficient parameterized algorithm for m-set packing. J. Algorithms\u00a050, 106\u2013117 (2004)","journal-title":"J. Algorithms"},{"key":"52_CR17","unstructured":"Karp, R.M.: Dynamic programming meets the principle of inclusion and exclusion. Oper. Res. Lett. 1, 49\u201351 (1982)"},{"key":"52_CR18","doi-asserted-by":"crossref","unstructured":"Kennes, R.: Computational aspects of the Moebius transform on a graph. IEEE Transactions on System, Man, and Cybernetics 22, 201\u2013223 (1991)","DOI":"10.1109\/21.148425"},{"key":"52_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/11917496_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Kneis","year":"2006","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: Divide-and-color. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 58\u201367. Springer, Heidelberg (2006)"},{"key":"52_CR20","first-page":"294","volume-title":"ACM Annual Conference (ACM\u00a01977)","author":"S. Kohn","year":"1977","unstructured":"Kohn, S., Gottlieb, A., Kohn, M.: A generating function approach to the traveling salesman problem. In: ACM Annual Conference (ACM\u00a01977), pp. 294\u2013300. ACM Press, New York (1977)"},{"key":"52_CR21","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.ipl.2004.12.005","volume":"94","author":"I. Koutis","year":"2005","unstructured":"Koutis, I.: A faster parameterized algorithm for set packing. Information Processing Letters\u00a094, 4\u20137 (2005)","journal-title":"Information Processing Letters"},{"key":"52_CR22","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":"52_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1007\/978-3-642-02927-1_54","volume-title":"ICALP 2009. Part I","author":"I. Koutis","year":"2009","unstructured":"Koutis, I., Williams, R.: Limitations 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":"52_CR24","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On limited nondeterminism and the complexity of the V-C dimension. J. Comput. Syst. Sci. 53, 161\u2013170 (1996)"},{"key":"52_CR25","doi-asserted-by":"crossref","unstructured":"Pohl, I.: Bi-directional and heuristic search in path problems. PhD thesis, Report SLAC-104, Stanford University (1969)","DOI":"10.2172\/4785039"},{"key":"52_CR26","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. In: 41st ACM Symposium on Theory of Computing (STOC\u00a02009), pp. 455\u2013464 (2009)","DOI":"10.1145\/1536414.1536477"},{"key":"52_CR27","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*O*(2 k ) time. Information Processing Letters\u00a0109, 315\u2013318 (2009)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:22:14Z","timestamp":1558524134000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}