Quadratic vertex kernel for rainbow matching

DOI10.1007/S00453-019-00618-0zbMath1435.68236OpenAlexW2969646029WikidataQ127355484 ScholiaQ127355484MaRDI QIDQ2300725

Sushmita Gupta, Sanjukta Roy, Meirav Zehavi, Saket Saurabh

Publication date: 28 February 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00618-0

zbMATH Keywords

parameterized complexitypolynomial kernelrainbow matching

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
• Fundamentals of parameterized complexity
• How many colors guarantee a rainbow matching?
• Multicolored matchings in hypergraphs
• Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs
• Rainbow matchings in properly edge colored graphs
• Rainbow matching in edge-colored graphs
• Heterochromatic matchings in edge-colored graphs
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• A rainbow \(k\)-matching in the complete graph with \(r\) colors
• NP-completeness of some generalizations of the maximum matching problem
• An approximate version of a conjecture of Aharoni and Berger
• Parameterized algorithms and kernels for rainbow matching
• Existences of rainbow matchings and rainbow matching covers
• Rainbow matchings in \(r\)-partite \(r\)-graphs
• Complexity results for rainbow matchings
• Large Rainbow Matchings in Edge-Coloured Graphs
• Edge Dominating Sets in Graphs
• Two-Commodity Flow
• Paths, Trees, and Flowers
• Parameterized Algorithms

This page was built for publication: Quadratic vertex kernel for rainbow matching