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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic

61 Citaten (Scopus)

143 Downloads (Pure)

Samenvatting

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)|

Originele taal-2	Engels
Pagina's (van-tot)	263-299
Tijdschrift	Theory of Computing Systems
Volume	53
DOI's	https://doi.org/10.1007/s00224-012-9393-4
Status	Gepubliceerd - 21 dec. 2010
Extern gepubliceerd	Ja

Toegang tot document

10.1007/s00224-012-9393-4

pdfFinale auteursversie , 703 KB

Citeer dit

@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

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit