An improved kernelization for P₂-packing
From MaRDI portal
Publication:991748
DOI10.1016/J.IPL.2009.12.002zbMATH Open1206.68354OpenAlexW2001191566MaRDI QIDQ991748FDOQ991748
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
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
Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)
Cites Work
- On the Complexity of General Graph Factor Problems
- Faster Algebraic Algorithms for Path and Packing Problems
- On the completeness of a generalized matching problem
- Graph-Theoretic Concepts in Computer Science
- Looking at the stars
- Maximum bounded \(H\)-matching is Max SNP-complete
- 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
- A parameterized perspective on packing paths of length two
- Improved Deterministic Algorithms for Weighted Matching and Packing Problems
Cited In (23)
- Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
- Matching and \(P _{2}\)-packing: weighted versions
- 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
- Title not available (Why is that?)
- 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
- An Improvement in the Two-packing Bound Related to Vizing's Conjecture
- A parameterized perspective on packing paths of length two
- Almost Induced Matching: Linear Kernels and Parameterized Algorithms
- 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
- An Improved Parameterized Algorithm for a Generalized Matching Problem
- 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)
