An Isomorphism Between Subexponential and Parameterized Complexity Theory
- 1 January 2007
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 37 (4), 1228-1258
- https://doi.org/10.1137/070687153
Abstract
No abstract availableThis publication has 11 references indexed in Scilit:
- Strong computational lower bounds via parameterized complexityJournal of Computer and System Sciences, 2006
- On miniaturized problems in parameterized complexity theoryTheoretical Computer Science, 2006
- Bounded fixed-parameter tractability and nondeterministic bitsJournal of Computer and System Sciences, 2006
- Tight lower bounds for certain parameterized NP-hard problemsInformation and Computation, 2005
- An improved deterministic local search algorithm for 3-SATTheoretical Computer Science, 2004
- On the existence of subexponential parameterized algorithmsJournal of Computer and System Sciences, 2003
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- Fixed-Parameter Tractability and Completeness I: Basic ResultsSIAM Journal on Computing, 1995
- Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analoguesAnnals of Pure and Applied Logic, 1995
- Fixed-parameter tractability and completeness II: On completeness for W[1]Theoretical Computer Science, 1995