An improved kernelization for P₂-packing

DOI10.1016/J.IPL.2009.12.002MaRDI QIDQ991748zbMATH OpenOpenAlexFDO

Authors Jianxin Wang, Dan Ning, Qilong Feng, Jianer 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

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

Recommendations

• Kernelization for \(P_2\)-packing: a gerrymandering approach
• An improved kernelization algorithm for \(r\)-set packing
• Kernelization of packing problems
• Kernels for Packing and Covering Problems
• Stronger bounds and faster algorithms for packing in generalized kernel systems
• Matching and weighted \(P_2\)-packing: algorithms and kernels
• A \(5k\)-vertex kernel for \(P_2\)-packing
• An improved kernel for planar vertex-disjoint triangle packing
• Kernelization algorithms for packing problems allowing overlaps
• Kernels for packing and covering problems

Cites work

• A parameterized perspective on packing paths of length two
• Faster Algebraic Algorithms for Path and Packing Problems
• Graph-Theoretic Concepts in Computer Science
• Improved Deterministic Algorithms for Weighted Matching and Packing Problems
• Looking at the stars
• 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
• On the completeness of a generalized matching problem

Cited in

(25)

• Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
• Matching and \(P _{2}\)-packing: weighted versions
• Almost induced matching: linear kernels and parameterized algorithms
• A Quadratic Kernel for 3-Set Packing
• Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
• Parameterized algorithms and kernels for almost induced matching
• On maximum \(P_3\)-packing in claw-free subcubic graphs
• Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
• An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs
• A 2k-kernelization algorithm for vertex cover based on crown decomposition
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Stronger bounds and faster algorithms for packing in generalized kernel systems
• Matching and weighted \(P_2\)-packing: algorithms and kernels
• An Improvement in the Two-packing Bound Related to Vizing's Conjecture
• A parameterized perspective on packing paths of length two
• A \(5k\)-vertex kernel for \(P_2\)-packing
• An improved kernelization algorithm for \(r\)-set packing
• A Parameterized Perspective on Packing Paths of Length Two
• Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
• Kernelization of packing problems
• An Improved Parameterized Algorithm for a Generalized Matching Problem
• Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
• Kernels for packing and covering problems
• A \(5k\)-vertex kernel for 3-path vertex cover
• Kernels for Packing and Covering Problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991748)