A 5k-vertex kernel for P2-packing

Wenjun Li; Junjie Ye; Yixin Cao

doi:10.1016/j.tcs.2022.01.032

A 5k-vertex kernel for P2-packing

Wenjun Li
, Junjie Ye
, Yixin Cao

Research output: Journal article publication › Journal article › Academic research › peer-review

1 Citation (Scopus)

Abstract

The P ₂-packing problem asks whether a graph contains k vertex-disjoint (not necessarily induced) paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel.

Original language	English
Pages (from-to)	1-13
Number of pages	13
Journal	Theoretical Computer Science
Volume	910
Issue number	1
DOIs	https://doi.org/10.1016/j.tcs.2022.01.032
Publication status	Published - 2 Apr 2022

Keywords

Crown decomposition
Kernelization algorithm
P2-packing

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

More information

10.1016/j.tcs.2022.01.032

http://hdl.handle.net/10397/99111

Cite this

@article{2d429b9363c04250a9c0d2d7f286b442,

title = "A 5k-vertex kernel for P2-packing",

abstract = "The P 2-packing problem asks whether a graph contains k vertex-disjoint (not necessarily induced) paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel.",

keywords = "Crown decomposition, Kernelization algorithm, P2-packing",

author = "Wenjun Li and Junjie Ye and Yixin Cao",

note = "Funding Information: Supported by the National Natural Science Foundation of China (NSFC) under grant 61872048 and the Research Foundation of Education Bureau of Hunan Province under grant 21B0305.Supported in part by the Hong Kong Research Grants Council (RGC) under grants 15221420 and 15201317, and the National Natural Science Foundation of China (NSFC) under grant 61972330. Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",

year = "2022",

month = apr,

day = "2",

doi = "10.1016/j.tcs.2022.01.032",

language = "English",

volume = "910",

pages = "1--13",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A 5k-vertex kernel for P2-packing

AU - Li, Wenjun

AU - Ye, Junjie

AU - Cao, Yixin

N1 - Funding Information: Supported by the National Natural Science Foundation of China (NSFC) under grant 61872048 and the Research Foundation of Education Bureau of Hunan Province under grant 21B0305.Supported in part by the Hong Kong Research Grants Council (RGC) under grants 15221420 and 15201317, and the National Natural Science Foundation of China (NSFC) under grant 61972330. Publisher Copyright: © 2022 Elsevier B.V.

PY - 2022/4/2

Y1 - 2022/4/2

N2 - The P 2-packing problem asks whether a graph contains k vertex-disjoint (not necessarily induced) paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel.

AB - The P 2-packing problem asks whether a graph contains k vertex-disjoint (not necessarily induced) paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel.

KW - Crown decomposition

KW - Kernelization algorithm

KW - P2-packing

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

U2 - 10.1016/j.tcs.2022.01.032

DO - 10.1016/j.tcs.2022.01.032

M3 - Journal article

SN - 0304-3975

VL - 910

SP - 1

EP - 13

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -

A 5k-vertex kernel for P2-packing

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this