A kernel of order 2k-c for Vertex Cover

Arezou Soleimanfallah; Anders Yeo

doi:10.1016/j.disc.2011.02.014

A kernel of order 2k-c for Vertex Cover

Arezou Soleimanfallah
, Anders Yeo

Royal Holloway University of London

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

Abstract

The best known kernel for the vertex cover problem was of order 2k for a long time, by a result of Chen et al. Recently, results by Chlebík and Clebíková, have implied that this can be improved to 2k-1. In this paper, we provide a new structural result which can be used to improve this to 2k-c, for any constant c.

Original language	English
Pages (from-to)	892-895
Number of pages	4
Journal	Discrete Mathematics
Volume	311
Issue number	10-11
DOIs	https://doi.org/10.1016/j.disc.2011.02.014
Publication status	Published - 6 Jun 2011
Externally published	Yes

Keywords

Fixed parameter tractable
Kernel
Vertex Cover

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2011.02.014

Cite this

@article{664e0a7bc10b44259adece8328e80d97,

title = "A kernel of order 2k-c for Vertex Cover",

abstract = "The best known kernel for the vertex cover problem was of order 2k for a long time, by a result of Chen et al. Recently, results by Chleb{\'i}k and Cleb{\'i}kov{\'a}, have implied that this can be improved to 2k-1. In this paper, we provide a new structural result which can be used to improve this to 2k-c, for any constant c.",

keywords = "Fixed parameter tractable, Kernel, Vertex Cover",

author = "Arezou Soleimanfallah and Anders Yeo",

year = "2011",

month = jun,

day = "6",

doi = "10.1016/j.disc.2011.02.014",

language = "English",

volume = "311",

pages = "892--895",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "10-11",

}

TY - JOUR

T1 - A kernel of order 2k-c for Vertex Cover

AU - Soleimanfallah, Arezou

AU - Yeo, Anders

PY - 2011/6/6

Y1 - 2011/6/6

N2 - The best known kernel for the vertex cover problem was of order 2k for a long time, by a result of Chen et al. Recently, results by Chlebík and Clebíková, have implied that this can be improved to 2k-1. In this paper, we provide a new structural result which can be used to improve this to 2k-c, for any constant c.

AB - The best known kernel for the vertex cover problem was of order 2k for a long time, by a result of Chen et al. Recently, results by Chlebík and Clebíková, have implied that this can be improved to 2k-1. In this paper, we provide a new structural result which can be used to improve this to 2k-c, for any constant c.

KW - Fixed parameter tractable

KW - Kernel

KW - Vertex Cover

UR - https://www.scopus.com/pages/publications/79952353118

U2 - 10.1016/j.disc.2011.02.014

DO - 10.1016/j.disc.2011.02.014

M3 - Article

AN - SCOPUS:79952353118

SN - 0012-365X

VL - 311

SP - 892

EP - 895

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10-11

ER -

A kernel of order 2k-c for Vertex Cover

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this