A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees

arXiv1207.6090MaRDI QIDQ6234645FDOQ6234645

Publication date: 25 July 2012

Abstract: Here we present a new fixed parameter tractable algorithm to compute the hybridization number r of two rooted, not necessarily binary phylogenetic trees on taxon set X in time (6^r.r!).poly(n)$, where n=|X|. The novelty of this approach is its use of terminals, which are maximal elements of a natural partial order on X, and several insights from the softwired clusters literature. This yields a surprisingly simple and practical bounded-search algorithm and offers an alternative perspective on the underlying combinatorial structure of the hybridization number problem.

This page was built for publication: A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees

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