{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T14:14:53Z","timestamp":1762352093019},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230717"},{"type":"electronic","value":"9783540286394"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-28639-4_25","type":"book-chapter","created":{"date-parts":[[2010,9,20]],"date-time":"2010-09-20T20:25:35Z","timestamp":1285014335000},"page":"281-290","source":"Crossref","is-referenced-by-count":48,"title":["Space and Time Complexity of Exact Algorithms: Some Open Problems"],"prefix":"10.1007","author":[{"given":"Gerhard J.","family":"Woeginger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0020-0190(93)90033-6","volume":"47","author":"E.T. Bax","year":"1993","unstructured":"Bax, E.T.: Inclusion and exclusion algorithm for the Hamiltonian path problem. Information Processing Letters\u00a047, 203\u2013207 (1993)","journal-title":"Information Processing Letters"},{"key":"25_CR2","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(94)00151-0","volume":"52","author":"E.T. Bax","year":"1994","unstructured":"Bax, E.T.: Algorithms to count paths and cycles. Information Processing Letters\u00a052, 249\u2013252 (1994)","journal-title":"Information Processing Letters"},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0020-0190(96)00159-7","volume":"60","author":"E.T. Bax","year":"1996","unstructured":"Bax, E.T., Franklin, J.: A finite-difference sieve to count paths and cycles by length. Information Processing Letters\u00a060, 171\u2013176 (1996)","journal-title":"Information Processing Letters"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proceedings of the 15th Annual ACM Symposium on the Theory of Computing (STOC 1983), pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"key":"25_CR5","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, 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/0022-0000(78)90026-0","volume":"16","author":"D. Dobkin","year":"1978","unstructured":"Dobkin, D., Lipton, R.J.: A lower bound of \n                  \n                    \n                  \n                  $\\frac{1}{2}$\n                 n2 on linear search programs for the knapsack problem. Journal of Computer and System Sciences\u00a016, 413\u2013417 (1978)","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR7","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science\u00a0141, 109\u2013131 (1995)","journal-title":"Theoretical Computer Science"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer Monographs in Computer Science (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., Grandoni, F.: On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science (2004) (to appear)","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-540-45078-8_27","volume-title":"Algorithms and Data Structures","author":"D. Eppstein","year":"2003","unstructured":"Eppstein, D.: The traveling salesman problem for cubic graphs. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 307\u2013318. Springer, Heidelberg (2003)"},{"key":"25_CR11","unstructured":"Erickson, J.: Lower bounds for linear satisfiability problems. Chicago Journal of Theoretical Computer Science 1999(8)"},{"key":"25_CR12","unstructured":"Erickson, J.: Private communication (2004)"},{"key":"25_CR13","first-page":"129","volume":"293","author":"S.S. Fedin","year":"2002","unstructured":"Fedin, S.S., Kulikov, A.S.: Solution of the maximum cut problem in time 2|E|\/4 (In Russian). Zapiski Nauchnykh Seminarov Sankt-Peterburgskoe Otdeleniya Matematicheski\u012d Institut imeni V.A. Steklova\u00a0293, 129\u2013138 (2002)","journal-title":"Zapiski Nauchnykh Seminarov Sankt-Peterburgskoe Otdeleniya Matematicheski\u012d Institut imeni V.A. Steklova"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J.: On limited versus polynomial nondeterminism. Chicago Journal of Theoretical Computer Science (1997)","DOI":"10.4086\/cjtcs.1997.001"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A. Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of O(n2) problems in computational geometry. Computational Geometry\u00a05, 165\u2013185 (1995)","journal-title":"Computational Geometry"},{"key":"25_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"25_CR17","first-page":"196","volume":"10","author":"M. Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. Journal of SIAM\u00a010, 196\u2013210 (1962)","journal-title":"Journal of SIAM"},{"key":"25_CR18","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. Journal of the ACM\u00a021, 277\u2013292 (1974)","journal-title":"Journal of the ACM"},{"key":"25_CR19","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, 413\u2013423 (1978)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0167-6377(82)90044-X","volume":"1","author":"R.M. Karp","year":"1982","unstructured":"Karp, R.M.: Dynamic programming meets the principle of inclusion and exclusion. Operations Research Letters\u00a01, 49\u201351 (1982)","journal-title":"Operations Research Letters"},{"key":"25_CR21","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"E.L. Lawler","year":"1976","unstructured":"Lawler, E.L.: A note on the complexity of the chromatic number problem. Information Processing Letters\u00a05, 66\u201367 (1976)","journal-title":"Information Processing Letters"},{"key":"25_CR22","first-page":"415","volume":"26","author":"J. Ne\u0161et\u0159il","year":"1985","unstructured":"Ne\u0161et\u0159il, J., Poljak, S.: On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae\u00a026, 415\u2013419 (1985)","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"25_CR23","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R. Schroeppel","year":"1981","unstructured":"Schroeppel, R., Shamir, A.: A T = O(2\n                           n\/2), S = O(2\n                           n\/4) algorithm for certain NP-complete problems. SIAM Journal on Computing\u00a010, 456\u2013464 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR24","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R.E. Tarjan","year":"1977","unstructured":"Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM Journal on Computing\u00a06, 537\u2013546 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1007\/978-3-540-27836-8_101","volume-title":"Automata, Languages and Programming","author":"R. Williams","year":"2004","unstructured":"Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1227\u20131237. Springer, Heidelberg (2004)"},{"key":"25_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"}],"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-540-28639-4_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:29:58Z","timestamp":1620012598000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-28639-4_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230717","9783540286394"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-28639-4_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}