Phylogenetic networks are directed graphs used to represent evolutionary histories in the presence of events in which several entities may combine to form a new one. Their reconstruction based on biological data is notoriously hard, and the problem of comparing networks arises in the validation of reconstruction methods. In this talk, I will present recent developments regarding the comparison of phylogenetic networks through the computation of a maximum common edge-contraction of two input networks. I will review links with contraction problems on undirected graphs, a NP-hardness result, and perspectives for parameterized algorithms.
Reference: [ https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.16 ]
[Bertrand Marchand] (University of Sherbrooke)
[ https://www.unravel.rwth-aachen.de/cms/unravel/das-graduiertenkolleg/te… ]
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .