A linear kernel for co-path/cycle packing

DOI10.1007/978-3-642-14355-7_10MaRDI QIDQ3578360zbMATH OpenOpenAlexWikidataFDO

Authors Zhi-Zhong Chen, Michael R. Fellows, Bin Fu, Haitao Jiang, Yang Liu, Lusheng Wang, Binhai Zhu

Publication date 20 July 2010

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

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• A parameterized algorithm for bounded-degree vertex deletion
• A quartic kernel for pathwidth-one vertex deletion
• Planar vertex-disjoint cycle packing: new structures and improved kernel
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
• A generalization of Nemhauser and Trotter's local optimization theorem

Cited in

(20)

• Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
• On structural parameterizations of the bounded-degree vertex deletion problem
• Kernels for packing and covering problems
• Randomized parameterized algorithms for P₂-packing and co-path packing problems
• Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths
• A parameterized algorithm for bounded-degree vertex deletion
• On structural parameterizations of the bounded-degree vertex deletion problem
• Approximating partially bounded degree deletion on directed graphs
• Approximating bounded degree deletion via matroid matching
• Approximating power node-deletion problems
• On the Parameterized Complexity of Maximum Degree Contraction Problem.
• A generalization of Nemhauser and Trotter's local optimization theorem
• Approximating power node-deletion problems
• Solving Co-Path/Cycle Packing and Co-Path Packing faster than \(3^k\)
• Structural parameterizations of the biclique-free vertex deletion problem
• Solving Co-Path/Cycle Packing and Co-Path Packing faster than \(3^k\)
• On bounded-degree vertex deletion parameterized by treewidth
• On the parameterized complexity of maximum degree contraction problem

This page was built for publication: A linear kernel for co-path/cycle packing

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