Better lower and upper bounds for the minimum rainbow subgraph problem

DOI10.1016/J.TCS.2014.05.008MaRDI QIDQ2250438zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmscombinatorial problemsminimum rainbow subgraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Approximating the rainbow -- better lower and upper bounds
• Improved approximation bounds for the minimum rainbow subgraph problem
• Algorithmic approaches for the minimum rainbow subgraph problem
• Approximation algorithms for the minimum rainbow subgraph problem
• Revisiting a randomized algorithm for the minimum rainbow subgraph problem

Cites work

• A polynomial case of the parsimony haplotyping problem
• A threshold of ln n for approximating set cover
• Algorithmic approaches for the minimum rainbow subgraph problem
• Approximation algorithms for the minimum rainbow subgraph problem
• Complexity of finding dense subgraphs
• Feature Article—The Ellipsoid Method: A Survey
• Haplotyping populations by pure parsimony: complexity of exact and approximation algorithms
• scientific article; zbMATH DE number 434896 (Why is no real title available?)
• Improved approximation bounds for the minimum rainbow subgraph problem
• Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
• On restricted colourings of \(K_ n\)
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• Rainbow subgraphs in properly edge‐colored graphs
• Reducibility among combinatorial problems
• The pure parsimony haplotyping problem: overview and computational advances

Cited in

(8)

• The parameterized complexity of the rainbow subgraph problem
• Algorithmic approaches for the minimum rainbow subgraph problem
• Approximating the rainbow -- better lower and upper bounds
• On the minimum rainbow subgraph number of a graph
• The parameterized complexity of the rainbow subgraph problem
• Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
• Revisiting a randomized algorithm for the minimum rainbow subgraph problem
• Essentially tight bounds for rainbow cycles in proper edge-colourings

This page was built for publication: Better lower and upper bounds for the minimum rainbow subgraph problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2250438)