DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2008.1357

Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees

Authors: Viet Tung Hoang and Wing-Kin Sung

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract

Consider a set of labels $L$ and a set of trees ${mathcal T} = { {mathcal T}^{(1), {mathcal T}^{(2), ldots, {mathcal T}^{(k) $ where each tree ${mathcal T}^{(i)$ is distinctly leaf-labeled by some subset of $L$. 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. This problem finds applications in phylogenetics, database, and data mining. 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 geq 3$. This paper gives the first polynomial time algorithms for both MASP and MCSP when both $k$ and the maximum degree $D$ of the trees are constant.

Cite as

Viet Tung Hoang and Wing-Kin Sung. Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 361-372, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hoang_et_al:LIPIcs.STACS.2008.1357,
  author =	{Hoang, Viet Tung and Sung, Wing-Kin},
  title =	{{Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{361--372},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1357},
  URN =		{urn:nbn:de:0030-drops-13579},
  doi =		{10.4230/LIPIcs.STACS.2008.1357},
  annote =	{Keywords: Maximum agreement supertree, maximum compatible supertree}
}

Search Results

Documents authored by Hoang, Viet Tung

Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees

Abstract

Cite as

Thanks for your feedback!

Could not send message