Better lower and upper bounds for the minimum rainbow subgraph problem

DOI10.1016/j.tcs.2014.05.008zbMath1330.68344MaRDI QIDQ2250438

Alexandru Popa

Publication date: 7 July 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.05.008

zbMATH Keywords

combinatorial problems; approximation algorithms; minimum rainbow subgraph

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

68W20: Randomized algorithms

Related Items

Revisiting a randomized algorithm for the minimum rainbow subgraph problem, The parameterized complexity of the rainbow subgraph problem, The Parameterized Complexity of the Rainbow Subgraph Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for the minimum rainbow subgraph problem
• On restricted colourings of \(K_ n\)
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Complexity of finding dense subgraphs
• Improved approximation bounds for the minimum rainbow subgraph problem
• A polynomial case of the parsimony haplotyping problem
• Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms
• A threshold of ln n for approximating set cover
• Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
• The pure parsimony haplotyping problem: overview and computational advances
• Feature Article—The Ellipsoid Method: A Survey
• Rainbow subgraphs in properly edge‐colored graphs
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• Reducibility among Combinatorial Problems