Please use this identifier to cite or link to this item: https://doi.org/10.1007/s00453-004-1147-5
Title: Rooted maximum agreement supertrees
Authors: Jansson, J. 
Ng, J.H.-K.
Sadakane, K.
Sung, W.-K. 
Keywords: Algorithm
Computational complexity
Maximum agreement supertree
Phylogenetic tree
Rooted triplet
Issue Date: 2005
Citation: Jansson, J., Ng, J.H.-K., Sadakane, K., Sung, W.-K. (2005). Rooted maximum agreement supertrees. Algorithmica (New York) 43 (4) : 293-307. ScholarBank@NUS Repository. https://doi.org/10.1007/s00453-004-1147-5
Abstract: Given a set τ rooted, unordered trees, where each T i ∈ τ is distinctly leaf-labeled by a set Λ(T i) and where the sets Λ(T i) may overlap, the maximum agreement supertree problem(MASP) is to construct a distinctly leaf-labeled tree script Q sign with leaf set Λ(script Q sign) ⊆ ∪ Ti ∈ τ Λ(T i) such that |Λ(script Q sign)| is maximized and for each T i ∈ Τ, the topological restriction of T i to Λ(script Q sign) is isomorphic to the topological restriction of script Q sign to Λ(T i). Let n = |∪ Ti ∈ τ Λ(T i)|, k = |Τ|, and D = max Ti ∈ Τ {deg(T i)}. We first show that MASP with k = 2 can be solved in O(√Dn log (2n/D)) time, which is O(n log n) when D = O(1) and O(n 1.5) when D is unrestricted. We then present an algorithm for MASP with D = 2 whose running time is polynomial if k = O(1). On the other hand, we prove that MASP is NP-hard for any fixed k ≥ 3 when D is unrestricted, and also NP-hard for any fixed D ≥ 2 when k is unrestricted even if each input tree is required to contain at most three leaves. Finally, we describe a polynomial-time (n/log n)-approximation algorithm for MASP. © 2005 Springer Science+Business Media, Inc.
Source Title: Algorithmica (New York)
URI: http://scholarbank.nus.edu.sg/handle/10635/39450
ISSN: 01784617
DOI: 10.1007/s00453-004-1147-5
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

29
checked on May 21, 2018

WEB OF SCIENCETM
Citations

26
checked on May 21, 2018

Page view(s)

58
checked on May 19, 2018

Google ScholarTM

Check

Altmetric


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