A 5k-vertex kernel for P2-packing

Wenjun Li, Junjie Ye, Yixin Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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.

Original languageEnglish
Pages (from-to)1-13
Number of pages13
JournalTheoretical Computer Science
Volume910
Issue number1
DOIs
Publication statusPublished - 2 Apr 2022

Keywords

  • Crown decomposition
  • Kernelization algorithm
  • P2-packing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this