A quadratic kernel for computing the hybridization number of multiple trees

Journal article (2013)

Authors

L.J.J. van Iersel Centrum Wiskunde & Informatica (CWI)
Simone Linz Eberhard Karls Universität Tübingen
Affiliation
External organisation
More Info
expand_more

Published Date

2013

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

Abstract

It has recently been shown that the NP-hard problem of calculating the minimum number of hybridization events that is needed to explain a set of rooted binary phylogenetic trees by means of a hybridization network is fixed-parameter tractable if an instance of the problem consists of precisely two such trees. In this paper, we show that this problem remains fixed-parameter tractable for an arbitrarily large set of rooted binary phylogenetic trees. In particular, we present a quadratic kernel.