The parameterized complexity of the rainbow subgraph problem

DOI10.3390/a8010060zbMath1461.68092OpenAlexW2126883946MaRDI QIDQ1736640

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

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a8010060

zbMATH Keywords

fixed-parameter tractabilityAPX-hardnessmultivariate complexity analysisproblem kernelhaplotypingparameterized hardness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Approximation algorithms for the minimum rainbow subgraph problem
• On the parameterized complexity of multiple-interval graph problems
• 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
• Parametrized complexity theory.
• On the minimum rainbow subgraph number of a graph
• The Design of Approximation 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
• Extended Islands of Tractability for Parsimony Haplotyping
• Haplotype Inference Constrained by Plausible Haplotype Data
• Finding Dense Subgraphs of Sparse Graphs
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: The parameterized complexity of the rainbow subgraph problem