Kernelization for P2-packing: A gerrymandering approach

Wenjun Li; Junjie Ye; Yixin Cao

doi:10.1007/978-3-319-78455-7_11

Kernelization for P₂-packing: A gerrymandering approach

Wenjun Li, Junjie Ye, Yixin Cao

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

2 Citations (Scopus)

Abstract

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

Original language	English
Title of host publication	Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings
Editors	Pinyan Lu, Jianer Chen
Publisher	Springer-Verlag
Pages	140-153
Number of pages	14
ISBN (Print)	9783319784540
DOIs	https://doi.org/10.1007/978-3-319-78455-7_11
Publication status	Published - 1 Jan 2018
Event	12th International Frontiers of Algorithmics Workshop, FAW 2018 - Guangzhou, China Duration: 8 May 2018 → 10 May 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10823 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Frontiers of Algorithmics Workshop, FAW 2018
Country	China
City	Guangzhou
Period	8/05/18 → 10/05/18

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

More information

10.1007/978-3-319-78455-7_11

Cite this

Li, W., Ye, J., & Cao, Y. (2018). Kernelization for P₂-packing: A gerrymandering approach. In P. Lu, & J. Chen (Eds.), Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings (pp. 140-153). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10823 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-319-78455-7_11

Li, Wenjun ; Ye, Junjie ; Cao, Yixin. / Kernelization for P₂-packing : A gerrymandering approach. Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings. editor / Pinyan Lu ; Jianer Chen. Springer-Verlag, 2018. pp. 140-153 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d3c72879d1424575a856e8de2bfd8762,

title = "Kernelization for P2-packing: A gerrymandering approach",

abstract = "The P2-packing problem asks for whether a graph contains k vertex-disjoint paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel.",

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

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-78455-7_11",

language = "English",

isbn = "9783319784540",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "140--153",

editor = "Pinyan Lu and Jianer Chen",

booktitle = "Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings",

note = "12th International Frontiers of Algorithmics Workshop, FAW 2018 ; Conference date: 08-05-2018 Through 10-05-2018",

}

Li, W, Ye, J & Cao, Y 2018, Kernelization for P₂-packing: A gerrymandering approach. in P Lu & J Chen (eds), Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10823 LNCS, Springer-Verlag, pp. 140-153, 12th International Frontiers of Algorithmics Workshop, FAW 2018, Guangzhou, China, 8/05/18. https://doi.org/10.1007/978-3-319-78455-7_11

Kernelization for P₂-packing : A gerrymandering approach. / Li, Wenjun; Ye, Junjie; Cao, Yixin.

Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings. ed. / Pinyan Lu; Jianer Chen. Springer-Verlag, 2018. p. 140-153 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10823 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Kernelization for P2-packing

T2 - 12th International Frontiers of Algorithmics Workshop, FAW 2018

AU - Li, Wenjun

AU - Ye, Junjie

AU - Cao, Yixin

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The P2-packing problem asks for whether a graph contains k vertex-disjoint paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel.

AB - The P2-packing problem asks for whether a graph contains k vertex-disjoint paths each of length two. We continue the study of its kernelization algorithms, and develop a 5k-vertex kernel.

UR - http://www.scopus.com/inward/record.url?scp=85046771230&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-78455-7_11

DO - 10.1007/978-3-319-78455-7_11

M3 - Conference article published in proceeding or book

AN - SCOPUS:85046771230

SN - 9783319784540

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 140

EP - 153

BT - Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings

A2 - Lu, Pinyan

A2 - Chen, Jianer

PB - Springer-Verlag

Y2 - 8 May 2018 through 10 May 2018

ER -

Li W, Ye J, Cao Y. Kernelization for P₂-packing: A gerrymandering approach. In Lu P, Chen J, editors, Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings. Springer-Verlag. 2018. p. 140-153. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-78455-7_11