Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40567
Title: Fixed parameter polynomial time algorithms for maximum agreement and compatible supertrees
Authors: Hoang, V.T.
Sung, W.-K. 
Keywords: Maximum agreement supertree
Maximum compatible supertree
Issue Date: 2008
Source: Hoang, V.T.,Sung, W.-K. (2008). Fixed parameter polynomial time algorithms for maximum agreement and compatible supertrees. Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 : 361-372. ScholarBank@NUS Repository.
Abstract: Consider a set of labels L and a set of trees T = {T (1),T (2),... , T k} where each tree T (i) is distinctly leaf-labeled by some subset of L. One fundamental problem is to find the biggest tree (denoted as supertree) to represent T which minimizes the disagreements with the trees in T under certain criteria. This problem finds applications in phylogenetics, database, and data mining. In this paper, we focus on two particular supertree problems, namely, the maximum agreement supertree problem (MASP) and the maximum compatible supertree problem (MCSP). These two problems are known to be NP-hard for k ≥ 3. This paper gives the first polynomial time algorithms for both MASP and MCSP when both k and the maximum degree D of the trees are constant.
Source Title: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008
URI: http://scholarbank.nus.edu.sg/handle/10635/40567
ISBN: 9783939897064
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

49
checked on Jan 19, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.