Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets

DOI10.1137/140981290zbMath1330.68111OpenAlexW1849484511MaRDI QIDQ3195130

Neeldhara Misra, Meirav Zehavi, Fahad Panolan, Prachi Goyal

Publication date: 21 October 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/140981290

zbMATH Keywords

set packingfixed-parameter algorithms3D-matchingiterative expansion\(r\)-dimensional matchingrepresentative sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (8)

Randomized parameterized algorithms for the kidney exchange problem ⋮ Parameterized approximation algorithms for packing problems ⋮ A multivariate framework for weighted FPT algorithms ⋮ Parameterized algorithms for graph partitioning problems ⋮ Unnamed Item ⋮ Representative families: a unified tradeoff-based approach ⋮ Representative families for matroid intersections, with applications to location, packing, and covering problems ⋮ The \(k\)-distinct language: parameterized automata constructions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Improved deterministic algorithms for weighted matching and packing problems
• Parameterized coloring problems on chordal graphs
• Refined memorization for vertex cover
• Faster fixed-parameter tractable algorithms for matching and packing problems
• A faster parameterized algorithm for set packing
• Using nondeterminism to design efficient deterministic algorithms
• Narrow sieves for parameterized paths and packings
• Parametrized complexity theory.
• Representative Sets of Product Families
• Representative Families: A Unified Tradeoff-Based Approach
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Iterative Expansion and Color Coding
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• Improved Parameterized Algorithms for Weighted 3-Set Packing
• Faster Algebraic Algorithms for Path and Packing Problems
• Limits and Applications of Group Algebras for Parameterized Problems
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Color-coding
• Multiplying matrices faster than coppersmith-winograd
• On generalized graphs

This page was built for publication: Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets