From the 1 of 11 linked papers with an AI index.
11 papers
Maximizing All-Paths Phylogenetic Diversity: Parameterized Approaches for Networks
Mark Jones, Jannik Schestag
The paper investigates the problem of maximizing a generalized phylogenetic diversity measure on directed acyclic phylogenetic networks, showing hardness results and presenting fix…
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…
Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth
Niels Holtgrefe, Jannik Schestag
Identifying a subset of taxa that maximizes Phylogenetic Diversity (PD) is a cornerstone of quantitative conservation planning. Traditionally, PD is defined over a phylogenetic tre…
Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility
Leo van Iersel, Mark Jones, Jannik Schestag +2
We investigate parameterized algorithms for computing the average-tree phylogenetic diversity (APD) in rooted phylogenetic networks, studying the problem under different structural…
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…