- Title
- The Computer Journal special issue on parameterized complexity: foreword by the guest editors (editorial)
- Creator
- Downey, Rodney G.; Fellows, Michael R.; Langston, Michael A.
- Relation
- Computer Journal Vol. 51, Issue 1, p. 1-6
- Publisher Link
- http://dx.doi.org/10.1093/comjnl/bxm111
- Publisher
- Oxford University Press
- Resource Type
- journal article
- Date
- 2008
- Description
- Parameterized complexity studies a generalization of the notion of polynomial time where, in addition to the overall input size n, one also considers the effects on computational complexity of a secondary measurement, the parameter. The central notion of the field is fixed-parameter tractability (FPT), which refers to solvability in time f(k)nc, where f is some function (usually exponential) of the parameter k, and c is a constant. The subject unfolds in two basic complementary projects and associated mathematical toolkits: (1) How to design (and improve) FPT algorithms, for parameterized problems that admit them and (2) How to gather evidence that a parameterized problem probably does not admit an FPT algorithm. This Special Issue of surveys of various aspects of parameterized complexity and algorithmics began on the suggestion of the Editor-in-Chief, Fionn Murtagh, who after hearing a broad account of the field at a colloquium at Royal Holloway, University of London, declared, "This is a subject that every computer scientist should know about".
- Subject
- parameterized complexity; polynomial time; fixed-parameter tractability (FPT); algorithmics
- Identifier
- http://hdl.handle.net/1959.13/41312
- Identifier
- uon:4731
- Identifier
- ISSN:0010-4620
- Language
- eng
- Hits: 957
- Visitors: 917
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|