Kernelization for P2-packing: A gerrymandering approach

Wenjun Li, Junjie Ye, Yixin Cao

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings
EditorsPinyan Lu, Jianer Chen
PublisherSpringer-Verlag
Pages140-153
Number of pages14
ISBN (Print)9783319784540
DOIs
Publication statusPublished - 1 Jan 2018
Event12th International Frontiers of Algorithmics Workshop, FAW 2018 - Guangzhou, China
Duration: 8 May 201810 May 2018

Publication series

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

Conference

Conference12th International Frontiers of Algorithmics Workshop, FAW 2018
Country/TerritoryChina
CityGuangzhou
Period8/05/1810/05/18

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this