2008/04/03 by Jianer Chen, Chen, Jianer, Henning Fernau +7
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems #Optimization and Packing Problems #cs.CC #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0804.0570
arxiv created 2008/04/03 · openalex publication_date 2008/04/03 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study (vertex-disjoint) P2-packings in graphs under a parameterized perspective. Starting from a maximal P2-packing \p of size j we use extremal arguments for determining how many vertices of \p appear in some P2-packing of size (j+1). We basically can 'reuse' 2.5j vertices. We also present a kernelization algorithm that gives a kernel of size bounded by 7k. With these two results we build an algorithm which constructs a P2-packing of size k in time \Oh^*(2.4823k).