An improved kernelization for \(P_{2}\)-packing

DOI10.1016/j.ipl.2009.12.002zbMath1206.68354OpenAlexW2001191566MaRDI QIDQ991748

Dan Ning, Jianxin Wang, Qilong Feng, Jian'er Chen

Publication date: 7 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.12.002

zbMATH Keywords

combinatorial problemskernelizationcrown decomposition\(P_{2}\)-packing

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (14)

Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique ⋮ Parameterized algorithms and kernels for almost induced matching ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Kernels for packing and covering problems ⋮ On maximum \(P_3\)-packing in claw-free subcubic graphs ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps ⋮ Unnamed Item ⋮ A \(5k\)-vertex kernel for \(P_2\)-packing

Cites Work

• Looking at the stars
• A parameterized perspective on packing paths of length two
• Maximum bounded \(H\)-matching is Max SNP-complete
• On the Complexity of General Graph Factor Problems
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Faster Algebraic Algorithms for Path and Packing Problems
• Improved Deterministic Algorithms for Weighted Matching and Packing Problems
• On the completeness of a generalized matching problem
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: An improved kernelization for \(P_{2}\)-packing