Name
Title | ||
|---|---|---|
Greedy Localization, Iterative Compression, Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for Set Splitting, and a Novel 2k Kernelization for Vertex Cover |
Abstract | ||
|---|---|---|
The two objectives of this paper are: (1) to articulate three new general techniques for designing FPT algorithms, and (2) to apply these to obtain new FPT algorithms for SET SPLITTING and VERTEX COVER. In the case of SET SPLITTING, we improve the best previous O*(72(k)) FPT algorithm due to Dehne, Fellows and Rosamond [DFR03], to O*(8(k)) by an approach based on greedy localization in conjunction with modeled crown reduction. In the case of VERTEX COVER, we describe a new approach to 2k kernelization based on iterative compression and crown reduction, providing a potentially useful alternative to the Nemhauser-Totter 2k kernelization. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-28639-4_24 | LECTURE NOTES IN COMPUTER SCIENCE |
Keywords | DocType | Volume |
vertex cover | Conference | 3162 |
ISSN | Citations | PageRank |
0302-9743 | 28 | 1.55 |
References | Authors | |
14 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank Dehne | 1 | 518 | 43.70 |
| Michael R. Fellows | 2 | 4138 | 319.37 |
| Frances A. Rosamond | 3 | 304 | 15.94 |
| Peter Shaw | 4 | 92 | 6.34 |