Please use this identifier to cite or link to this item:
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.
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)
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.


checked on Oct 30, 2020


checked on Oct 30, 2020

Page view(s)

checked on Oct 25, 2020

Google ScholarTM



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