Name
Abstract | ||
|---|---|---|
Kernelization is a central technique used in parameterized algorithms, and in other approaches for coping with NP-hard problems. In this paper, we introduce a new method which allows us to show that many problems do not have polynomial size kernels under reasonable complexity-theoretic assumptions. These problems include k -Path, k -Cycle, k -Exact Cycle, k -Short Cheap Tour, k -Graph Minor Order Test, k -Cutwidth, k -Search Number, k -Pathwidth, k -Treewidth, k -Branchwidth, and several optimization problems parameterized by treewidth or cliquewidth. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-70575-8_46 | ICALP |
Keywords | Field | DocType |
polynomial kernels,parameterized algorithm,short cheap tour,exact cycle,extended abstract,polynomial size kernel,optimization problem,new method,central technique,search number,np-hard problem,graph minor order test,graph minor | Kernelization,Polynomial hierarchy,Discrete mathematics,Parameterized complexity,Combinatorics,Polynomial,Polynomial kernel,Vertex cover,Treewidth,Graph minor,Mathematics | Conference |
Volume | ISSN | Citations |
5125 | 0302-9743 | 50 |
PageRank | References | Authors |
2.13 | 34 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hans L. Bodlaender | 1 | 5699 | 375.15 |
| Rodney G. Downey | 2 | 2082 | 207.92 |
| Michael R. Fellows | 3 | 4138 | 319.37 |
| Danny Hermelin | 4 | 790 | 48.62 |