Parameterized algorithms and kernels for rainbow matching

DOI10.1007/s00453-018-0497-3zbMath1422.68188OpenAlexW2885052028WikidataQ129408940 ScholiaQ129408940MaRDI QIDQ1739114

Sanjukta Roy, Meirav Zehavi, Saket Saurabh, Sushmita Gupta

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

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

Mathematics Subject Classification ID

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

Related Items (2)

Quadratic vertex kernel for rainbow matching ⋮ Parameterized complexity of maximum edge colorable subgraph

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