Abstract
We discuss open questions around worst case time and space bounds for NP-hard problems. We are interested in exponential time solutions for these problems with a relatively good worst case behavior.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bax, E.T.: Inclusion and exclusion algorithm for the Hamiltonian path problem. Information Processing Letters 47, 203–207 (1993)
Bax, E.T.: Algorithms to count paths and cycles. Information Processing Letters 52, 249–252 (1994)
Bax, E.T., Franklin, J.: A finite-difference sieve to count paths and cycles by length. Information Processing Letters 60, 171–176 (1996)
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–86 (1983)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation 9, 251–280 (1990)
Dobkin, D., Lipton, R.J.: A lower bound of \(\frac{1}{2}\) n2 on linear search programs for the knapsack problem. Journal of Computer and System Sciences 16, 413–417 (1978)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science 141, 109–131 (1995)
Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer Monographs in Computer Science (1999)
Eisenbrand, F., Grandoni, F.: On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science (2004) (to appear)
Eppstein, D.: The traveling salesman problem for cubic graphs. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 307–318. Springer, Heidelberg (2003)
Erickson, J.: Lower bounds for linear satisfiability problems. Chicago Journal of Theoretical Computer Science 1999(8)
Erickson, J.: Private communication (2004)
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ĭ Institut imeni V.A. Steklova 293, 129–138 (2002)
Feige, U., Kilian, J.: On limited versus polynomial nondeterminism. Chicago Journal of Theoretical Computer Science (1997)
Gajentaan, A., Overmars, M.H.: On a class of O(n2) problems in computational geometry. Computational Geometry 5, 165–185 (1995)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. Journal of SIAM 10, 196–210 (1962)
Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. Journal of the ACM 21, 277–292 (1974)
Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM Journal on Computing 7, 413–423 (1978)
Karp, R.M.: Dynamic programming meets the principle of inclusion and exclusion. Operations Research Letters 1, 49–51 (1982)
Lawler, E.L.: A note on the complexity of the chromatic number problem. Information Processing Letters 5, 66–67 (1976)
Nešetřil, J., Poljak, S.: On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae 26, 415–419 (1985)
Schroeppel, R., Shamir, A.: A T = O(2n/2), S = O(2n/4) algorithm for certain NP-complete problems. SIAM Journal on Computing 10, 456–464 (1981)
Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM Journal on Computing 6, 537–546 (1977)
Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1227–1237. Springer, Heidelberg (2004)
Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol. 2570, pp. 185–207. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Woeginger, G.J. (2004). Space and Time Complexity of Exact Algorithms: Some Open Problems. In: Downey, R., Fellows, M., Dehne, F. (eds) Parameterized and Exact Computation. IWPEC 2004. Lecture Notes in Computer Science, vol 3162. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28639-4_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-28639-4_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23071-7
Online ISBN: 978-3-540-28639-4
eBook Packages: Springer Book Archive