Vertex cover kernelization revisited: upper and lower bounds for a refined parameter

B.M.P. Jansen; H.L. Bodlaender

doi:10.1007/s00224-012-9393-4

Vertex cover kernelization revisited: upper and lower bounds for a refined parameter

B.M.P. Jansen, H.L. Bodlaender

Research output: Contribution to journal › Article › Academic

56 Citations (Scopus)

127 Downloads (Pure)

Abstract

An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G',k') in polynomial time with the guarantee that G' has at most 2k' vertices (and thus O((k')^2) edges) with k' |V(G)|

Original language	English
Pages (from-to)	263-299
Journal	Theory of Computing Systems
Volume	53
DOIs	https://doi.org/10.1007/s00224-012-9393-4
Publication status	Published - 21 Dec 2010
Externally published	Yes

Keywords

cs.DS
cs.CC
F.2.2

Access to Document

10.1007/s00224-012-9393-4

pdfFinal author version , 703 KB

Cite this

@article{ea0d3cefd2274c6c8b75244ce5c8ead5,

title = "Vertex cover kernelization revisited: upper and lower bounds for a refined parameter",

abstract = "An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G',k') in polynomial time with the guarantee that G' has at most 2k' vertices (and thus O((k')\textasciicircum{}2) edges) with k' |V(G)|",

keywords = "cs.DS, cs.CC, F.2.2",

author = "B.M.P. Jansen and H.L. Bodlaender",

year = "2010",

month = dec,

day = "21",

doi = "10.1007/s00224-012-9393-4",

language = "English",

volume = "53",

pages = "263--299",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer",

}

TY - JOUR

T1 - Vertex cover kernelization revisited

T2 - upper and lower bounds for a refined parameter

AU - Jansen, B.M.P.

AU - Bodlaender, H.L.

PY - 2010/12/21

Y1 - 2010/12/21

N2 - An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G',k') in polynomial time with the guarantee that G' has at most 2k' vertices (and thus O((k')^2) edges) with k' |V(G)|

AB - An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G',k') in polynomial time with the guarantee that G' has at most 2k' vertices (and thus O((k')^2) edges) with k' |V(G)|

KW - cs.DS

KW - cs.CC

KW - F.2.2

U2 - 10.1007/s00224-012-9393-4

DO - 10.1007/s00224-012-9393-4

M3 - Article

SN - 1432-4350

VL - 53

SP - 263

EP - 299

JO - Theory of Computing Systems

JF - Theory of Computing Systems

ER -

Vertex cover kernelization revisited: upper and lower bounds for a refined parameter

Abstract

Keywords

Access to Document

Fingerprint

Cite this