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
Source: 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

28
checked on Dec 7, 2017

WEB OF SCIENCETM
Citations

24
checked on Nov 29, 2017

Page view(s)

52
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


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