Improved approximation bounds for the minimum rainbow subgraph problem

DOI10.1016/j.ipl.2010.11.005zbMath1259.05167OpenAlexW2045197802MaRDI QIDQ1944047

Ingo Schiermeyer, Ján Katrenič

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.11.005

zbMATH Keywords

approximation algorithmNP-hardminimum rainbow subgraph problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the approximability of the minimum rainbow subgraph problem and other related problems ⋮ The Parameterized Complexity of the Rainbow Subgraph Problem ⋮ The parameterized complexity of the rainbow subgraph problem ⋮ Revisiting a randomized algorithm for the minimum rainbow subgraph problem ⋮ Better lower and upper bounds for the minimum rainbow subgraph problem ⋮ Unnamed Item ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

Cites Work

• Approximation algorithms for the minimum rainbow subgraph problem
• On packing shortest cycles in graphs
• Exponential-time approximation of weighted set cover
• A polynomial case of the parsimony haplotyping problem
• Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms
• From the theory of regular graphs of third and fourth degree
• Color-coding
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved approximation bounds for the minimum rainbow subgraph problem