48 citations · 69 across the 9 of their papers we have counts for
11 papers
Neighbor Joining And Leaf Status
Mathias Weller
The Neighbor Joining Algorithm is among the most fundamental algorithmic results in computational biology. However, its definition and correctness proof are not straightforward. In…
Embedding phylogenetic trees in networks of low treewidth
Leo van Iersel, Mark Jones, Mathias Weller
Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called \textsc{Tree Containment}, arise…
Listing Conflicting Triples in Optimal Time
Mathias Weller
Different sources of information might tell different stories about the evolutionary history of a given set of species. This leads to (rooted) phylogenetic trees that "disagree" on…
Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series
Vincent Froese, Brijnesh Jain, Maciej Rymar +1
Dynamic Time Warping (DTW) is a well-known similarity measure for time series. The standard dynamic programming approach to compute the DTW distance of two length- time series,…
What is known about Vertex Cover Kernelization?
Michael R. Fellows, Lars Jaffke, Aliz Izabella Király +2
We are pleased to dedicate this survey on kernelization of the Vertex Cover problem, to Professor Juraj Hromkovič on the occasion of his 60th birthday. The Vertex Cover problem is…
Constructing a Consensus Phylogeny from a Leaf-Removal Distance
Cedric Chauve, Mark Jones, Manuel Lafond +2
Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. The problem we study here takes as input a set of trees describing {possi…
Linear-Time Tree Containment in Phylogenetic Networks
Mathias Weller
We consider the NP-hard Tree Containment problem that has important applications in phylogenetics. The problem asks if a given leaf-labeled network contains a subdivision of a give…
On the Complexity of Hub Labeling
Maxim Babenko, Andrew V. Goldberg, Haim Kaplan +2
Hub Labeling (HL) is a data structure for distance oracles. Hierarchical HL (HHL) is a special type of HL, that received a lot of attention from a practical point of view. However,…
Optimal Hub Labeling is NP-complete
Mathias Weller
Distance labeling is a preprocessing technique introduced by Peleg [Journal of Graph Theory, 33(3)] to speed up distance queries in large networks. Herein, each vertex receives a (…
A Polynomial-time Algorithm for Outerplanar Diameter Improvement
Nathann Cohen, Daniel Gonçalves, Eun Jung Kim +4
The Outerplanar Diameter Improvement problem asks, given a graph and an integer , whether it is possible to add edges to in a way that the resulting graph is outerplanar…
Interval scheduling and colorful independent sets
René van Bevern, Matthias Mnich, Rolf Niedermeier +1
Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an…