Options
Kernel and fast algorithm for dense triplet inconsistency
Publikationstyp
Journal Article
Date Issued
2013-01-02
Sprache
English
Author(s)
TORE-URI
Journal
Start Page
134
End Page
143
Citation
Theoretical Computer Science (2013)
Publisher DOI
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