A Linear Kernel for Co-Path/Cycle Packing

DOI10.1007/978-3-642-14355-7_10zbMath1286.05131OpenAlexW2166321766WikidataQ57359728 ScholiaQ57359728MaRDI QIDQ3578360

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

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)

Related Items (16)

Approximating Bounded Degree Deletion via Matroid Matching ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ Approximating power node-deletion problems ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Kernels for packing and covering problems ⋮ A Parameterized Algorithm for Bounded-Degree Vertex Deletion ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing} ⋮ Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems

This page was built for publication: A Linear Kernel for Co-Path/Cycle Packing