Matching and weighted P₂-packing: algorithms and kernels
DOI10.1016/J.TCS.2013.12.011zbMATH Open1279.68101OpenAlexW1986069448MaRDI QIDQ393902FDOQ393902
Authors: Qilong Feng, Jianxin Wang, Jianer 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
Recommendations
- Matching and \(P _{2}\)-packing: weighted versions
- An improved kernelization for \(P_{2}\)-packing
- An Improved Parameterized Algorithm for a Generalized Matching Problem
- Parameterized algorithms for weighted matching and packing problems
- Parameterized Algorithms for Weighted Matching and Packing Problems
Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- On the Complexity of General Graph Factor Problems
- Improved parameterized set splitting algorithms: A Probabilistic approach
- Approximation algorithms for the test cover problem
- Title not available (Why is that?)
- An Improved Parameterized Algorithm for a Generalized Matching Problem
- Faster Algebraic Algorithms for Path and Packing Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the completeness of a generalized matching problem
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- Looking at the stars
- Approximation algorithms for some vehicle routing problems
- Title not available (Why is that?)
- Maximum bounded \(H\)-matching is Max SNP-complete
- 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
- A parameterized perspective on packing paths of length two
- An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
- An approximation algorithm for maximum triangle packing
- Improved Deterministic Algorithms for Weighted Matching and Packing Problems
- The P k Partition Problem and Related Problems in Bipartite Graphs
Cited In (14)
- Parameterized algorithms for weighted matching and packing problems
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- Parameterized approximation algorithms for packing problems
- Matching and \(P _{2}\)-packing: weighted versions
- Parameterized and approximation algorithms for finding two disjoint matchings
- An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
- On maximum \(P_3\)-packing in claw-free subcubic graphs
- Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
- An improved kernelization for \(P_{2}\)-packing
- Parameterized Algorithms for Weighted Matching and Packing Problems
- An Improved Parameterized Algorithm for a Generalized Matching Problem
- Improved kernel results for some FPT problems based on simple observations
- Partition on trees with supply and demand: kernelization and algorithms
- Kernels for packing and covering problems
This page was built for publication: Matching and weighted \(P_2\)-packing: algorithms and kernels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393902)
