Please use this identifier to cite or link to this item: https://doi.org/10.1007/s00453-009-9303-6
Title: Improved algorithms for maximum agreement and compatible supertrees
Authors: Hoang, V.T.
Sung, W.-K. 
Keywords: Maximum agreement supertree
Maximum compatible supertree
Phylogenetic tree
Suptree
Issue Date: 2011
Source: Hoang, V.T., Sung, W.-K. (2011). Improved algorithms for maximum agreement and compatible supertrees. Algorithmica (New York) 59 (2) : 195-214. ScholarBank@NUS Repository. https://doi.org/10.1007/s00453-009-9303-6
Abstract: Consider a set of labels L and a set of unordered 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. 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 improved algorithms for both MASP and MCSP. In particular, our results imply the first polynomial time algorithms for both MASP and MCSP when both k and the maximum degree D of the input trees are constant. © 2009 Springer Science+Business Media, LLC.
Source Title: Algorithmica (New York)
URI: http://scholarbank.nus.edu.sg/handle/10635/39091
ISSN: 01784617
DOI: 10.1007/s00453-009-9303-6
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

2
checked on Dec 7, 2017

WEB OF SCIENCETM
Citations

1
checked on Nov 22, 2017

Page view(s)

51
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


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