A linear kernel for co-path/cycle packing
DOI10.1007/978-3-642-14355-7_10zbMATH Open1286.05131OpenAlexW2166321766WikidataQ57359728 ScholiaQ57359728MaRDI QIDQ3578360FDOQ3578360
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
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
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)
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 structural parameterizations of the bounded-degree vertex deletion problem
- Approximating partially bounded degree deletion on directed graphs
- On bounded-degree vertex deletion parameterized by treewidth
- 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
- A parameterized algorithm for bounded-degree vertex deletion
- Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
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)
