Improved approximation bounds for the minimum rainbow subgraph problem
type: Item
instance of: scholarly article
title: Improved approximation bounds for the minimum rainbow subgraph problem
zbMATH Open document ID: 1259.05167
author: Ján Katrenič
author: Ingo Schiermeyer
published in: Information Processing Letters
publication date: 2013-04-04T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6150237
zbMATH Keywords: minimum rainbow subgraph problem
zbMATH Keywords: approximation algorithm
zbMATH Keywords: NP-hard
MaRDI profile type: Publication
full work available at URL: j.ipl.2010.11.005
OpenAlex ID: W2045197802
cites work: Color-coding
cites work: Q3619846
cites work: Exponential-time approximation of weighted set cover
cites work: Q4142699
cites work: From the theory of regular graphs of third and fourth degree
cites work: Haplotyping populations by pure parsimony: complexity of exact and approximation algorithms
cites work: A polynomial case of the parsimony haplotyping problem
cites work: Approximation algorithms for the minimum rainbow subgraph problem
cites work: On packing shortest cycles in graphs
DOI: 10.1016/J.IPL.2010.11.005
description: scientific article; zbMATH DE number 6150237