Greedy localization, iterative compression, and modeled crown reductions: new fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover

F Dehne; M. Fellows; F. Rosamond; P. Shaw

doi:10.1007/978-3-540-28639-4_24

Greedy localization, iterative compression, and modeled crown reductions: new fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover

F Dehne, M. Fellows, F. Rosamond, P. Shaw

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings

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*(72k) FPT algorithm due to Dehne, Fellows and Rosamond [DFR03], to O*(8k) 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-Trotter 2k kernelization. © Springer-Verlag 2004.

Original language	English
Title of host publication	Parameterized and Exact Computation
Subtitle of host publication	First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Proceedings
Editors	Rod Downey, Michael Fellows, Frank Dehne
Publisher	Springer
Pages	271-280
Number of pages	10
ISBN (Electronic)	978-3-540-28639-4
ISBN (Print)	978-3-540-23071-7
DOIs	https://doi.org/10.1007/978-3-540-28639-4_24
Publication status	Published - 2004
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	3162
ISSN (Print)	0302-9743

Cite this

Dehne, F., Fellows, M., Rosamond, F., & Shaw, P. (2004). Greedy localization, iterative compression, and modeled crown reductions: new fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In R. Downey, M. Fellows, & F. Dehne (Eds.), Parameterized and Exact Computation: First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Proceedings (pp. 271-280). (Lecture Notes in Computer Science ; Vol. 3162). Springer. https://doi.org/10.1007/978-3-540-28639-4_24

Dehne, F ; Fellows, M. ; Rosamond, F. ; Shaw, P. / Greedy localization, iterative compression, and modeled crown reductions : new fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. Parameterized and Exact Computation: First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Proceedings. editor / Rod Downey ; Michael Fellows ; Frank Dehne. Springer, 2004. pp. 271-280 (Lecture Notes in Computer Science ).

@inproceedings{af41719ad4d84f5fbad920ca54ce4d39,

title = "Greedy localization, iterative compression, and 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*(72k) FPT algorithm due to Dehne, Fellows and Rosamond [DFR03], to O*(8k) 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-Trotter 2k kernelization. {\circledC} Springer-Verlag 2004.",

keywords = "Algorithms, FPT algorithms, Kernelization, New approaches, Set splitting, Vertex cover, Iterative methods",

author = "F Dehne and M. Fellows and F. Rosamond and P. Shaw",

year = "2004",

doi = "10.1007/978-3-540-28639-4_24",

language = "English",

isbn = "978-3-540-23071-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "271--280",

editor = "Rod Downey and Michael Fellows and Frank Dehne",

booktitle = "Parameterized and Exact Computation",

address = "Switzerland",

}

Dehne, F, Fellows, M, Rosamond, F & Shaw, P 2004, Greedy localization, iterative compression, and modeled crown reductions: new fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. in R Downey, M Fellows & F Dehne (eds), Parameterized and Exact Computation: First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Proceedings. Lecture Notes in Computer Science , vol. 3162, Springer, pp. 271-280. https://doi.org/10.1007/978-3-540-28639-4_24

Greedy localization, iterative compression, and modeled crown reductions : new fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. / Dehne, F; Fellows, M.; Rosamond, F.; Shaw, P.

Parameterized and Exact Computation: First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Proceedings. ed. / Rod Downey; Michael Fellows; Frank Dehne. Springer, 2004. p. 271-280 (Lecture Notes in Computer Science ; Vol. 3162).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings

TY - GEN

T1 - Greedy localization, iterative compression, and modeled crown reductions

T2 - new fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover

AU - Dehne, F

AU - Fellows, M.

AU - Rosamond, F.

AU - Shaw, P.

PY - 2004

Y1 - 2004

N2 - 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*(72k) FPT algorithm due to Dehne, Fellows and Rosamond [DFR03], to O*(8k) 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-Trotter 2k kernelization. © Springer-Verlag 2004.

AB - 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*(72k) FPT algorithm due to Dehne, Fellows and Rosamond [DFR03], to O*(8k) 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-Trotter 2k kernelization. © Springer-Verlag 2004.

KW - Algorithms, FPT algorithms

KW - Kernelization

KW - New approaches

KW - Set splitting

KW - Vertex cover, Iterative methods

UR - https://www.scopus.com/inward/record.uri?eid=2-s2.0-35048841147&partnerID=40&md5=2f4363e46e77419e2049d9194ab99d56

U2 - 10.1007/978-3-540-28639-4_24

DO - 10.1007/978-3-540-28639-4_24

M3 - Conference Paper published in Proceedings

SN - 978-3-540-23071-7

T3 - Lecture Notes in Computer Science

SP - 271

EP - 280

BT - Parameterized and Exact Computation

A2 - Downey, Rod

A2 - Fellows, Michael

A2 - Dehne, Frank

PB - Springer

ER -

Dehne F, Fellows M, Rosamond F, Shaw P. Greedy localization, iterative compression, and modeled crown reductions: new fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In Downey R, Fellows M, Dehne F, editors, Parameterized and Exact Computation: First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Proceedings. Springer. 2004. p. 271-280. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-540-28639-4_24

Access to Document

10.1007/978-3-540-28639-4_24

Link to Scopus publication