Polynomial Kernelization for Removing Induced Claws and Diamonds

Marek Cygan; Marcin Pilipczuk; Michał Pilipczuk; E.J. van Leeuwen; Marcin Wrochna

doi:10.1007/s00224-016-9689-x

Polynomial Kernelization for Removing Induced Claws and Diamonds

Marek Cygan
, Marcin Pilipczuk
, Michał Pilipczuk
, E.J. van Leeuwen
, Marcin Wrochna

University of Warsaw

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

Original language	English
Pages (from-to)	615-636
Number of pages	22
Journal	Theory of Computing Systems
Volume	60
Issue number	4
DOIs	https://doi.org/10.1007/s00224-016-9689-x
Publication status	Published - 2017

Keywords

Edge deletion
{claw, diamond}-free graphs
Parameterized complexity
Polynomial kernel

Access to Document

10.1007/s00224-016-9689-x

10.1007%2Fs00224-016-9689-xFinal published version, 619 KB

Cite this

@article{bf432ec801794c1aba248a38dbf65168,

title = "Polynomial Kernelization for Removing Induced Claws and Diamonds",

keywords = "Edge deletion, \{claw, diamond\}-free graphs, Parameterized complexity, Polynomial kernel",

author = "Marek Cygan and Marcin Pilipczuk and Micha{\l} Pilipczuk and \{van Leeuwen\}, E.J. and Marcin Wrochna",

year = "2017",

doi = "10.1007/s00224-016-9689-x",

language = "English",

volume = "60",

pages = "615--636",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Polynomial Kernelization for Removing Induced Claws and Diamonds

AU - Cygan, Marek

AU - Pilipczuk, Marcin

AU - Pilipczuk, Michał

AU - van Leeuwen, E.J.

AU - Wrochna, Marcin

PY - 2017

Y1 - 2017

KW - Edge deletion

KW - {claw, diamond}-free graphs

KW - Parameterized complexity

KW - Polynomial kernel

U2 - 10.1007/s00224-016-9689-x

DO - 10.1007/s00224-016-9689-x

M3 - Article

SN - 1432-4350

VL - 60

SP - 615

EP - 636

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 4

ER -