Better lower and upper bounds for the minimum rainbow subgraph problem
From MaRDI portal
Publication:2250438
DOI10.1016/j.tcs.2014.05.008zbMath1330.68344OpenAlexW1967845089MaRDI QIDQ2250438
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
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) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (3)
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
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
This page was built for publication: Better lower and upper bounds for the minimum rainbow subgraph problem
