The \textsc{Maximum Colorful Arborescence} problem: how (computationally) hard can it be?

DOI10.1016/j.tcs.2020.11.021zbMath1477.68224OpenAlexW3104225743MaRDI QIDQ2220833

Guillaume Fertin, Géraldine Jean, Julien Fradin

Publication date: 25 January 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.11.021

zbMATH Keywords

complexityapproximation algorithmsFPT algorithmsmaximum colorful arborescencetandem mass spectrometry

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Uses Software

• speedy_colorful_subtrees
• HMDB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity issues in vertex-colored graph pattern matching
• Which problems have strongly exponential complexity?
• Some results on more flexible versions of Graph Motif
• Algorithmic Aspects of the Maximum Colorful Arborescence Problem
• Speedy Colorful Subtrees
• The Maximum Colorful Arborescence problem parameterized by the structure of its color hierarchy graph
• Graph Motif Problems Parameterized by Dual
• Parameterized Algorithms
• Optimum branchings

This page was built for publication: The \textsc{Maximum Colorful Arborescence} problem: how (computationally) hard can it be?