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

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

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

(17)

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

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)