Algorithmic approaches for the minimum rainbow subgraph problem

MaRDI QIDQ2857441zbMATH OpenFDO

Authors Maria Koch, Stephan Matos Camacho, Ingo Schiermeyer

Publication date 1 November 2013

Full work available at URL http://www.sciencedirect.com/science/article/pii/S1571065311001946

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) Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for the minimum rainbow subgraph problem
• Improved approximation bounds for the minimum rainbow subgraph problem
• On the minimum rainbow subgraph number of a graph
• Better lower and upper bounds for the minimum rainbow subgraph problem
• Approximating the rainbow -- better lower and upper bounds

Cites work

• Approximation algorithms for the minimum rainbow subgraph problem
• Complexity of finding dense subgraphs
• Graph theory
• Improved approximation bounds for the minimum rainbow subgraph problem

Cited in

(12)

• On the approximability of the minimum rainbow subgraph problem and other related problems
• The parameterized complexity of the rainbow subgraph problem
• The rainbow spanning forest problem
• Improved approximation bounds for the minimum rainbow subgraph problem
• Better lower and upper bounds 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
• On the approximability of the minimum rainbow subgraph problem and other related problems
• Revisiting a randomized algorithm for the minimum rainbow subgraph problem
• Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
• Approximation algorithms for the minimum rainbow subgraph problem

This page was built for publication: Algorithmic approaches 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 Q2857441)