Algorithmics and Computational Complexity Research GroupTalk 24.10.2019

# Treewidth and Scanwidth in Phylogenetics

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


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

Date
Speaker
Location
Language
24.10.2019
16:15
Mathias Weller
TEL 512
English

Back to the research colloquium site.