An Improved Parameterized Algorithm for a Generalized Matching Problem

DOI10.1007/978-3-540-79228-4_19zbMath1139.68346OpenAlexW1551260816MaRDI QIDQ3502648

Qilong Feng, Dan Ning, Jianxin Wang, Jian'er Chen

Publication date: 27 May 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79228-4_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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths ⋮ Edge-disjoint packing of stars and cycles ⋮ A parameterized perspective on packing paths of length two ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ Matching and weighted \(P_2\)-packing: algorithms and kernels ⋮ Packing paths: recycling saves time ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ A Problem Kernelization for Graph Packing ⋮ A Parameterized Perspective on Packing Paths of Length Two

This page was built for publication: An Improved Parameterized Algorithm for a Generalized Matching Problem