Space and time complexity of exact algorithms : some open problems

G.J. Woeginger

doi:10.1007/978-3-540-28639-4_25

Space and time complexity of exact algorithms : some open problems

G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

72 Citations (Scopus)

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.

Original language	English
Title of host publication	Parametrized and Exact Computation (Proceedings First International Workshop, IWPEC2004, Bergen, Norway, September 14-17, 2004)
Editors	R. Downey, M. Fellows, F. Dehne
Place of Publication	Berlin
Publisher	Springer
Pages	281-290
ISBN (Print)	3-540-23071-8
DOIs	https://doi.org/10.1007/978-3-540-28639-4_25
Publication status	Published - 2004

Publication series

Name	Lecture Notes in Computer Science
Volume	3162
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-540-28639-4_25

Cite this

Woeginger, G. J. (2004). Space and time complexity of exact algorithms : some open problems. In R. Downey, M. Fellows, & F. Dehne (Eds.), Parametrized and Exact Computation (Proceedings First International Workshop, IWPEC2004, Bergen, Norway, September 14-17, 2004) (pp. 281-290). (Lecture Notes in Computer Science; Vol. 3162). Springer. https://doi.org/10.1007/978-3-540-28639-4_25

@inproceedings{e518a344c82f4f8eacafab1e55806da3,

title = "Space and time complexity of exact algorithms : some open problems",

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.",

author = "G.J. Woeginger",

year = "2004",

doi = "10.1007/978-3-540-28639-4_25",

language = "English",

isbn = "3-540-23071-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "281--290",

editor = "R. Downey and M. Fellows and F. Dehne",

booktitle = "Parametrized and Exact Computation (Proceedings First International Workshop, IWPEC2004, Bergen, Norway, September 14-17, 2004)",

address = "Germany",

}

Woeginger, GJ 2004, Space and time complexity of exact algorithms : some open problems. in R Downey, M Fellows & F Dehne (eds), Parametrized and Exact Computation (Proceedings First International Workshop, IWPEC2004, Bergen, Norway, September 14-17, 2004). Lecture Notes in Computer Science, vol. 3162, Springer, Berlin, pp. 281-290. https://doi.org/10.1007/978-3-540-28639-4_25

Space and time complexity of exact algorithms : some open problems. / Woeginger, G.J.
Parametrized and Exact Computation (Proceedings First International Workshop, IWPEC2004, Bergen, Norway, September 14-17, 2004). ed. / R. Downey; M. Fellows; F. Dehne. Berlin: Springer, 2004. p. 281-290 (Lecture Notes in Computer Science; Vol. 3162).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Space and time complexity of exact algorithms : some open problems

AU - Woeginger, G.J.

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-28639-4_25

DO - 10.1007/978-3-540-28639-4_25

M3 - Conference contribution

SN - 3-540-23071-8

T3 - Lecture Notes in Computer Science

SP - 281

EP - 290

BT - Parametrized and Exact Computation (Proceedings First International Workshop, IWPEC2004, Bergen, Norway, September 14-17, 2004)

A2 - Downey, R.

A2 - Fellows, M.

A2 - Dehne, F.

PB - Springer

CY - Berlin

ER -

Space and time complexity of exact algorithms : some open problems

Abstract

Publication series

Access to Document

Fingerprint

Cite this