Improved approximation bounds for the minimum rainbow subgraph problem
From MaRDI portal
Publication:1944047
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
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