Parameterized algorithms and kernels for rainbow matching

DOI10.1007/S00453-018-0497-3MaRDI QIDQ1739114zbMATH OpenOpenAlexWikidataFDO

Authors Sushmita Gupta, Sanjukta Roy, Saket Saurabh, Meirav Zehavi

Publication date 25 April 2019

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/8124/

zbMATH Keywords

3-dimensional matching3-set packingbounded search treesdivide-and-conquerparameterized algorithmrainbow matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Parameterized Algorithms and Kernels for Rainbow Matching
• Quadratic vertex kernel for rainbow matching
• Complexity results for rainbow matchings
• On the fine-grained complexity of rainbow coloring
• On the fine-grained complexity of rainbow coloring

Cites work

• A measure \& conquer approach for the analysis of exact algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An improved kernelization algorithm for \(r\)-set packing
• Complexity results for rainbow matchings
• Edge Dominating Sets in Graphs
• Exact exponential algorithms.
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Kernelization of packing problems
• Matching theory
• Mixing Color Coding-Related Techniques
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• Narrow sieves for parameterized paths and packings
• NP-completeness of some generalizations of the maximum matching problem
• Parameterized algorithms
• Paths, Trees, and Flowers
• Some Matching Problems for Bipartite Graphs

Cited in

(8)

• Parameterized complexity of maximum edge colorable subgraph
• The precise complexity of finding rainbow even matchings
• Quadratic vertex kernel for rainbow matching
• Complexity results for rainbow matchings
• Parameterized Algorithms and Kernels for Rainbow Matching
• Proportionally Fair Matching with Multiple Groups
• Solution discovery via reconfiguration for problems in P
• Stability in graphs with matroid constraints

This page was built for publication: Parameterized algorithms and kernels for rainbow matching

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