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

DOI10.1016/J.TCS.2020.11.021MaRDI QIDQ2220833zbMATH OpenOpenAlexFDO

Authors Guillaume Fertin, Julien Fradin, Géraldine Jean

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

approximation algorithmscomplexityFPT algorithmsmaximum colorful arborescencetandem mass spectrometry

Mathematics Subject Classification ID

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

Recommendations

• Algorithmic aspects of the maximum colorful arborescence problem
• On the maximum colorful arborescence problem and color hierarchy graph structure
• Speedy colorful subtrees
• Heuristic algorithms for the maximum colorful subtree problem

Cites work

• Algorithmic aspects of the maximum colorful arborescence problem
• Complexity issues in vertex-colored graph pattern matching
• Graph motif problems parameterized by dual
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 3285076 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On the maximum colorful arborescence problem and color hierarchy graph structure
• Optimum branchings
• Parameterized algorithms
• Some results on more flexible versions of Graph Motif
• Speedy colorful subtrees
• Which problems have strongly exponential complexity?

Cited in

(5)

• Algorithmic aspects of the maximum colorful arborescence problem
• Speedy colorful subtrees
• Heuristic algorithms for the maximum colorful subtree problem
• On the maximum colorful arborescence problem and color hierarchy graph structure
• On the complexity of temporal arborescence reconfiguration

Describes a project that uses

Uses Software

• speedy_colorful_subtrees
• HMDB

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220833)