Back to Search
Start Over
Kernelization: New Upper and Lower Bound Techniques.
- Source :
- Parameterized & Exact Computation (9783642112683); 2009, p17-37, 21p
- Publication Year :
- 2009
-
Abstract
- In this survey, we look at kernelization: algorithms that transform in polynomial time an input to a problem to an equivalent input, whose size is bounded by a function of a parameter. Several results of recent research on kernelization are mentioned. This survey looks at some recent results where a general technique shows the existence of kernelization algorithms for large classes of problems, in particular for planar graphs and generalizations of planar graphs, and recent lower bound techniques that give evidence that certain types of kernelization algorithms do not exist. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783642112683
- Database :
- Complementary Index
- Journal :
- Parameterized & Exact Computation (9783642112683)
- Publication Type :
- Book
- Accession number :
- 76743448
- Full Text :
- https://doi.org/10.1007/978-3-642-11269-0_2