Better lower and upper bounds for the minimum rainbow subgraph problem
From MaRDI portal
Publication:2250438
DOI10.1016/j.tcs.2014.05.008zbMath1330.68344MaRDI 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
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