Treewidth and Scanwidth in Phylogenetics

Mathias Weller (University of Eastern Paris - Marne-la-Vallée)

As efforts to support events causing incongruency in evolutionary scenarios
grow, computational phylogenetics develops the need for good parameters
capturing the hardness of many problems which were easy for evolutionary trees.
In recent years, theoretical results regarding the treewidth have been
published. In this talk, I will give a small overview over the current state of
the art regarding the use of treewidth in phylogenetics. Then, I will introduce
a new promising parameter called "scanwidth" which is particularly well suited
for dynamic programming on phylogenetic networks. Unfortunately, this width
parameter is NP-hard to compute.

Back to the research colloquium site.