Lower Bounds for Kernelizations and Other Preprocessing Procedures
- 26 May 2010
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 48 (4), 803-839
- https://doi.org/10.1007/s00224-010-9270-y
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization MappingJournal of Logic and Computation, 2008
- On Problems without Polynomial Kernels (Extended Abstract)Lecture Notes in Computer Science, 2008
- Invitation to data reduction and problem kernelizationACM SIGACT News, 2007
- The strong perfect graph theoremAnnals of Mathematics, 2006
- The complexity of first-order and monadic second-order logic revisitedAnnals of Pure and Applied Logic, 2004
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- SAT-Problems and Reductions with Respect to the Number of VariablesJournal of Logic and Computation, 1997
- On computing Boolean connectives of characteristic functionsTheory of Computing Systems, 1995
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1987
- Some consequences of non-uniform conditions on uniform classesTheoretical Computer Science, 1983