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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.ipl.2013.02.010 | Inf. Process. Lett. |
Keywords | Field | DocType |
rooted binary phylogenetic tree,fixed-parameter tractable,large set,multiple tree,hybridization number,minimum number,hybridization event,np-hard problem,hybridization network,quadratic kernel,hybridization,generator,phylogenetic network,computational complexity,kernel | Kernel (linear algebra),Discrete mathematics,Combinatorics,Phylogenetic tree,Quadratic equation,Arbitrarily large,Mathematics,Binary number,Phylogenetic network,Computational complexity theory | Journal |
Volume | Issue | ISSN |
113 | 9 | 0020-0190 |
Citations | PageRank | References |
5 | 0.48 | 13 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Leo van Iersel | 1 | 215 | 24.58 |
Simone Linz | 2 | 112 | 14.50 |