Kernelizations for the hybridization number problem on multiple nonbinary trees

L.J.J. van Iersel, Steven Kelk, Celine Scornavacca

Research output: Contribution to journalArticleScientificpeer-review

12 Citations (Scopus)

Abstract

Given a finite set X, a collection Tof rooted phylogenetic trees on Xand an integerk, theHybridization Numberproblem asks if there exists a phylogenetic network onXthat displays all trees fromTand has reticulation number at mostk. We show two kernelization algorithms forHybridization Number, with kernel sizes 4k(5k)tand 20k2(+−1)respectively, withtthe number of input trees and+their maximum outdegree. Experiments on simulated data demonstrate the practical relevance of our kernelization algorithms. In addition, we present an nf(k)t-time algorithm, with n =|X|and fsome computable function ofk.
Original languageEnglish
Pages (from-to)1075-1089
Number of pages15
JournalJournal of Computer and System Sciences
Volume82
Issue number6
DOIs
Publication statusPublished - 2016

Keywords

  • Fixed-parameter tractability
  • Kernelization
  • Phylogenetic tree
  • Phylogenetic network
  • Hybridization number

Fingerprint Dive into the research topics of 'Kernelizations for the hybridization number problem on multiple nonbinary trees'. Together they form a unique fingerprint.

Cite this