The Parameterized Complexity of the Rainbow Subgraph Problem

DOI10.1007/978-3-319-12340-0_24zbMath1417.68053OpenAlexW239606889MaRDI QIDQ2945198

Martin Rötzschke, Christian Komusiewicz, Rolf Niedermeier, Falk Hüffner

Publication date: 9 September 2015

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.650.8349

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

On the approximability of the minimum rainbow subgraph problem and other related problems

Cites Work

• Unnamed Item
• Approximation algorithms for the minimum rainbow subgraph problem
• Exponential-time approximation of weighted set cover
• Some APX-completeness results for cubic graphs
• Improved approximation bounds for the minimum rainbow subgraph problem
• Better lower and upper bounds for the minimum rainbow subgraph problem
• On the minimum rainbow subgraph number of a graph
• The Design of Approximation Algorithms
• A measure & conquer approach for the analysis of exact algorithms
• Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
• Fourier meets M\"{o}bius: fast subset convolution
• Set Partitioning via Inclusion-Exclusion
• Finding Dense Subgraphs of Sparse Graphs

This page was built for publication: The Parameterized Complexity of the Rainbow Subgraph Problem