5 papers
Orienting Unrooted Binary Networks Faster: Focus on the Generator
Jannik Schestag, Norbert Zeh
The problem of orienting an unrooted network to obtain a specific class of rooted phylogenetic networks is known to be NP-hard in many cases. In this paper, we introduce two algori…
When Many Trees Go to War: On Sets of Phylogenetic Trees With Almost No Common Structure
Mathias Weller, Norbert Zeh
It is known that any two trees on the same leaves can be displayed by a network with reticulations, and there are two trees that cannot be displayed by a network with few…
A Class of Unrooted Phylogenetic Networks Inspired by the Properties of Rooted Tree-Child Networks
Leo van Iersel, Mark Jones, Simone Linz +1
A directed phylogenetic network is tree-child if every non-leaf vertex has a child that is not a reticulation. As a class of directed phylogenetic networks, tree-child networks are…
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…
The First Known Problem That Is FPT with Respect to Node Scanwidth but Not Treewidth
Jannik Schestag, Norbert Zeh
Structural parameters of graphs, such as treewidth, play a central role in the study of the parameterized complexity of graph problems. Motivated by the study of parametrized algor…