Please use this identifier to cite or link to this item:

`https://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 |

Citation: | 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.

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