Approximation algorithms for the minimum rainbow subgraph problem

DOI10.1016/j.disc.2010.03.032zbMath1215.05181OpenAlexW2077912839MaRDI QIDQ709311

Zsolt Tuza, Ingo Schiermeyer, Stephan Matos Camacho

Publication date: 18 October 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2010.03.032

zbMATH Keywords

approximation algorithmedge colouringminimum rainbow subgraph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (7)

On the approximability of the minimum rainbow subgraph problem and other related problems ⋮ The Parameterized Complexity of the Rainbow Subgraph Problem ⋮ Improved approximation bounds for the minimum 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

Cites Work

• Unnamed Item
• Complexity of finding dense subgraphs
• 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
• Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: Approximation algorithms for the minimum rainbow subgraph problem