Matching and weighted \(P_2\)-packing: algorithms and kernels

DOI10.1016/j.tcs.2013.12.011zbMath1279.68101OpenAlexW1986069448MaRDI QIDQ393902

Qilong Feng, Jianxin Wang, Jian'er Chen

Publication date: 24 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.12.011

zbMATH Keywords

matchingkernelizationparameterized algorithmweighted \(P_2\)-packing

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) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (7)

Parameterized approximation algorithms for packing problems ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Partition on trees with supply and demand: kernelization and algorithms ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Kernels for packing and covering problems ⋮ On maximum \(P_3\)-packing in claw-free subcubic graphs ⋮ An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Looking at the stars
• A parameterized perspective on packing paths of length two
• Improved parameterized set splitting algorithms: A Probabilistic approach
• Maximum bounded \(H\)-matching is Max SNP-complete
• Approximation algorithms for the test cover problem
• Approximation algorithms for some vehicle routing problems
• An approximation algorithm for maximum triangle packing
• On the Complexity of General Graph Factor Problems
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• An Improved Parameterized Algorithm for a Generalized Matching Problem
• Faster Algebraic Algorithms for Path and Packing Problems
• Improved Deterministic Algorithms for Weighted Matching and Packing Problems
• On the completeness of a generalized matching problem
• The P k Partition Problem and Related Problems in Bipartite Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Matching and weighted \(P_2\)-packing: algorithms and kernels