Parameterized algorithms for weighted matching and packing problems

DOI10.1016/J.DISOPT.2008.07.002MaRDI QIDQ955335zbMATH OpenOpenAlexFDO

Authors Jianxin Wang, Yunlong Liu

Publication date 19 November 2008

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2008.07.002

zbMATH Keywords

parameterized algorithmsweighted \(m-D\) matching problemweighted \(m\)-set packing problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Parameterized Algorithms for Weighted Matching and Packing Problems
• Improved Deterministic Algorithms for Weighted Matching and Packing Problems
• Improved deterministic algorithms for weighted matching and packing problems
• Parameterized approximation algorithms for packing problems
• Matching and weighted \(P_2\)-packing: algorithms and kernels
• Algorithms – ESA 2004
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Efficient algorithms for variants of weighted matching and assignment problems
• Matching and \(P _{2}\)-packing: weighted versions
• On Counting Parameterized Matching and Packing

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Algorithms – ESA 2004
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• An efficient parameterized algorithm for m-set packing
• Color-coding
• Exact algorithms and applications for tree-like Weighted Set Cover
• Graph-Theoretic Concepts in Computer Science
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• Greedy local improvement and weighted set packing approximation
• Improved Parameterized Algorithms for Weighted 3-Set Packing
• Improved algorithms for path, matching, and packing problems
• Parameterized and Exact Computation

Cited in

(12)

• Algorithms – ESA 2004
• Parameterized approximation algorithms for packing problems
• Matching and weighted \(P_2\)-packing: algorithms and kernels
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Matching and \(P _{2}\)-packing: weighted versions
• Improved deterministic algorithms for weighted matching and packing problems
• Parameterized Weighted Containment
• Improved Deterministic Algorithms for Weighted Matching and Packing Problems
• Improved Algorithms for Weighted and Unweighted Set Splitting Problems
• Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
• Parameterized and approximation algorithms for finding two disjoint matchings
• Parameterized Algorithms for Weighted Matching and Packing Problems

This page was built for publication: Parameterized algorithms for weighted matching and packing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q955335)