Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39122
Title: Rooted maximum agreement supertrees
Authors: Jansson, J. 
Ng, J.H.-K.
Sadakane, K.
Sung, W.-K. 
Issue Date: 2004
Source: Jansson, J.,Ng, J.H.-K.,Sadakane, K.,Sung, W.-K. (2004). Rooted maximum agreement supertrees. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2976 : 499-508. ScholarBank@NUS Repository.
Abstract: Given a set Τ of 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 Q with leaf set Λ(Q) ⊆ ∪T i ∈Τ Λ(T i) such that |Λ(Q)| is maximized and for each T i ∈ Τ, the topological restriction of T i to Λ(Q) is isomorphic to the topological restriction of Q to Λ(T i). Let n = |∪T i∈ΤΛ(T i)|, k = |Τ|, and D = maxT i∈Τ{deg(T i)}. We first show that MASP with k = 2 can be solved in O(√D n 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. © Springer-Verlag 2004.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/39122
ISSN: 03029743
Appears in Collections:Staff Publications

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

Page view(s)

63
checked on Dec 8, 2017

Google ScholarTM

Check


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