Complexity results for rainbow matchings

DOI10.1016/j.tcs.2013.12.013zbMath1282.68195arXiv1312.7253OpenAlexW2034652539MaRDI QIDQ2637345

Van Bang Le, Florian Pfender

Publication date: 11 February 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1312.7253

zbMATH Keywords

computational complexityNP-completenessparameterized complexityrainbow matchingAPX-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (9)

Maximum 0-1 timed matching on temporal graphs ⋮ Color-line and proper color-line graphs ⋮ Integrality gaps for colorful matchings ⋮ Minimum <scp>color‐degree</scp> perfect b‐matchings ⋮ Parameterized algorithms and kernels for rainbow matching ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Unnamed Item ⋮ Quadratic vertex kernel for rainbow matching ⋮ Parameterized Algorithms and Kernels for Rainbow Matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Rainbow matchings of size \(\delta(G)\) in properly edge-colored graphs
• Rainbow matchings in properly edge colored graphs
• A note on large rainbow matchings in edge-coloured graphs
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• Optimization, approximation, and complexity classes
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Some APX-completeness results for cubic graphs
• Parametrized complexity theory.
• Large Rainbow Matchings in Edge-Coloured Graphs
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Some Matching Problems for Bipartite Graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Complexity results for rainbow matchings