Publications (19)
Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
Niels Holtgrefe, Jannik Schestag, Norbert Zeh
In the Maximize Phylogenetic Diversity problem, we are given a phylogenetic tree that represents the genetic proximity of species, and we are asked to select a subset of species of…
A Unifying Characterization of Tree-based Networks and Orchard Networks using Cherry Covers
Leo van Iersel, Remie Janssen, Mark Jones +2
Phylogenetic networks are used to study evolutionary relationships between species in biology. Such networks are often categorized into classes by their topological features, which…
A Simple 4-Approximation Algorithm for Maximum Agreement Forests on Multiple Unrooted Binary Trees
Jordan Dempsey, Leo van Iersel, Mark Jones +1
We present a simple 4-approximation algorithm for computing a maximum agreement forest of multiple unrooted binary trees. This algorithm applies LP rounding to an extension of a re…
A Wild Sheep Chase Through an Orchard
Jordan Dempsey, Leo van Iersel, Mark Jones +2
Orchards are a biologically relevant class of phylogenetic networks as they can describe treelike evolutionary histories augmented with horizontal transfer events. Moreover, the cl…
Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests
Chris Whidden, Robert G. Beiko, Norbert Zeh
We present new and improved fixed-parameter algorithms for computing maximum agreement forests (MAFs) of pairs of rooted binary phylogenetic trees. The size of such a forest for tw…
Another virtue of wavelet forests?
Christina Boucher, Travis Gagie, Aaron Hong +2
A wavelet forest for a text over an alphabet takes bits of space and supports access and rank on in time. Kärkkäinen…