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
fixed-parameter tractabilityAPX-hardnessmultivariate complexity analysisproblem kernelhaplotypingparameterized hardness
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
