Guillemot, SylvainSylvainGuillemotMnich, MatthiasMatthiasMnich2020-01-242020-01-242013-01-02Theoretical Computer Science (2013)http://hdl.handle.net/11420/4541Westudytheparameterizedcomplexityofinferringsupertreesfromsetsofrootedtriplets,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).en0304-39752013134143Elsevier BVInformatikBiowissenschaften, BiologieJournal Article10.1016/j.tcs.2012.12.032Other