Parameterized Algorithms and Kernels for Rainbow Matching

DOI10.4230/LIPIcs.MFCS.2017.71zbMath1435.68237OpenAlexW3163427696MaRDI QIDQ5111288

Sanjukta Roy, Sushmita Gupta, Saket Saurabh, Meirav Zehavi

Publication date: 26 May 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.71

zbMATH Keywords

divide-and-conquer3-dimensional matchingparameterized algorithmrainbow matching3-set packingbounded search trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

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

This page was built for publication: Parameterized Algorithms and Kernels for Rainbow Matching