18 citations · 79 across the 28 of their papers we have counts for
7 papers · 1 filter
Deep kernelization for the Tree Bisection and Reconnnect (TBR) distance in phylogenetics
Steven Kelk, Simone Linz, Ruben Meuwese
We describe a kernel of size 9k-8 for the NP-hard problem of computing the Tree Bisection and Reconnect (TBR) distance k between two unrooted binary phylogenetic trees. We achieve…
Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance
Steven Kelk, Simone Linz, Ruben Meuwese
The rooted subtree prune and regraft (rSPR) distance between two rooted binary phylogenetic trees is a well-studied measure of topological dissimilarity that is NP-hard to compute.…
A QUBO formulation for the Tree Containment problem
Michael J. Dinneen, Pankaj S. Ghodla, Simone Linz
Phylogenetic (evolutionary) trees and networks are leaf-labeled graphs that are widely used to represent the evolutionary relationships between entities such as species, languages,…
Quasi-Isometric Graph Simplifications
Khí-Uí Soo, Bakhadyr Khoussainov, Simone Linz
Quasi-isometries are mappings on graphs, with distance-distortions parameterized by a multiplicative factor and an additive constant. The distance-distortions of quasi-isometries a…
Reflections on kernelizing and computing unrooted agreement forests
Rim van Wersch, Steven Kelk, Simone Linz +1
Phylogenetic trees are leaf-labelled trees used to model the evolution of species. Here we explore the practical impact of kernelization (i.e. data reduction) on the NP-hard proble…
New reduction rules for the tree bisection and reconnection distance
Steven Kelk, Simone Linz
Recently it was shown that, if the subtree and chain reduction rules have been applied exhaustively to two unrooted phylogenetic trees, the reduced trees will have at most 15k-9 ta…