caa a22 4500 445805005 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s00453-009-9303-6 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9303-6 Improved Algorithms for Maximum Agreement andCompatible Supertrees [Elektronische Daten] [Viet Hoang, Wing-Kin Sung] Consider a set of labels L and a set of unordered trees $\mathcal{T}=\{\mathcal{T}^{(1)},\mathcal{T}^{(2)},\ldots ,\allowbreak \mathcal{T}^{(k)}\}$ where each tree $\mathcal{T}^{(i)}$ is distinctly leaf-labeled by some subset ofL. One fundamental problem is to find the biggest tree (denoted as supertree) to represent $\mathcal{T}$ which minimizes the disagreements with the trees in $\mathcal{T}$ under certain criteria. In this paper, we focus on two particular supertree problems, namely, the maximum agreement supertree problem (MASP) and the maximum compatible supertree problem (MCSP). These two problems are known to be NP-hard for k≥3. This paper gives improved algorithms for both MASP and MCSP. In particular, our results imply the first polynomial time algorithms for both MASP and MCSP when both k and the maximum degree D of the input trees are constant. Springer Science+Business Media, LLC, 2009 Phylogenetic tree nationallicence Suptree nationallicence Maximum agreement supertree nationallicence Maximum compatible supertree nationallicence Hoang Viet Department of Computer Science, National University of Singapore, Kent Ridge, Singapore aut Sung Wing-Kin Department of Computer Science, National University of Singapore, Kent Ridge, Singapore aut Algorithmica Springer-Verlag 59/2(2011-02-01), 195-214 0178-4617 59:2<195 2011 59 453 https://doi.org/10.1007/s00453-009-9303-6 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9303-6 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Hoang Viet Department of Computer Science, National University of Singapore, Kent Ridge, Singapore aut NATIONALLICENCE 700 1- Sung Wing-Kin Department of Computer Science, National University of Singapore, Kent Ridge, Singapore aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/2(2011-02-01), 195-214 0178-4617 59:2<195 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer