Kernels for Packing and Covering Problems

DOI10.1007/978-3-642-29700-7_19MaRDI QIDQ2897995zbMATH OpenOpenAlexFDO

Authors Jianer Chen, Henning Fernau, Peter R. Shaw, Jianxin Wang

Publication date 16 July 2012

Published in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-29700-7_19

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Kernels for packing and covering problems
• Kernelization of packing problems
• Kernelization algorithms for packing problems allowing overlaps
• Explicit linear kernels for packing problems
• Stronger bounds and faster algorithms for packing in generalized kernel systems
• An improved kernelization for \(P_{2}\)-packing
• A Problem Kernelization for Graph Packing
• An improved kernelization algorithm for \(r\)-set packing
• Kernelization for \(P_2\)-packing: a gerrymandering approach
• On kernels for covering and packing ILPs with small coefficients

Cited in

(17)

• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
• Kernels for packing and covering problems
• Parameterized algorithms and kernels for almost induced matching
• Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
• Edge-disjoint packing of stars and cycles
• An improved kernelization for \(P_{2}\)-packing
• Almost induced matching: linear kernels and parameterized algorithms
• A \(5k\)-vertex kernel for \(P_2\)-packing
• A measure and conquer approach for the parameterized bounded degree-one vertex deletion
• An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs
• A \(5k\)-vertex kernel for 3-path vertex cover
• Stronger bounds and faster algorithms for packing in generalized kernel systems
• On the vertex cover \(P_3\) problem parameterized by treewidth
• A Quadratic Kernel for 3-Set Packing
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• An improved kernelization algorithm for \(r\)-set packing

This page was built for publication: Kernels for Packing and Covering Problems

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