Kernel and fast algorithm for dense triplet inconsistency

Publikationstyp
Journal Article
Date Issued
2013-01-02
Sprache
English
Author(s)
Guillemot, Sylvain  
Mnich, Matthias  
TORE-URI
http://hdl.handle.net/11420/4541
Journal
Theoretical computer science  
Start Page
134
End Page
143
Citation
Theoretical Computer Science (2013)
Publisher DOI
10.1016/j.tcs.2012.12.032
Publisher
Elsevier BV
Westudytheparameterizedcomplexityofinferringsupertreesfromsetsofrootedtriplets,an important problem in phylogenetics. For a setLof labels and a dense setTof tripletsdistinctly leaf-labeled by 3-subsets ofL, we seek a tree distinctly leaf-labeled byLandcontainingallbutatmostktripletsfromTashomeomorphicsubtree.Ourresultsarethefirst polynomial kernel for this problem, withO(k2)labels, and a subexponential fixed-parameteralgorithmrunningintimeO(|L|4)+2O(k1/3logk).
DDC Class
004: Informatik
570: Biowissenschaften, Biologie