Scanning Phylogenetic Networks Is NP-hard

DOI10.1007/978-3-030-38919-2_42zbMath1440.92049OpenAlexW2999580712MaRDI QIDQ3297781

Mathias Weller, Vincent Berry, Celine Scornavacca

Publication date: 20 July 2020

Published in: SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal-upec-upem.archives-ouvertes.fr/hal-02353161/file/hrl.pdf

Mathematics Subject Classification ID

Problems related to evolution (92D15) Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
• On the fixed parameter tractability of agreement-based phylogenetic distances
• Compatibility of unrooted phylogenetic trees is FPT
• Treewidth distance on phylogenetic trees
• Directed path-width and monotonicity in digraph searching
• Fixed-Parameter Algorithms for Maximum Agreement Forests
• On Low Treewidth Graphs and Supertrees
• Complete Register Allocation Problems
• Reducibility among Combinatorial Problems

This page was built for publication: Scanning Phylogenetic Networks Is NP-hard