1 Search Results for "Hoang, Viet Tung"

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-dev.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}
}

Refine by Author
1 Hoang, Viet Tung
1 Sung, Wing-Kin

Refine by Classification

Refine by Keyword
1 Maximum agreement supertree
1 maximum compatible supertree

Refine by Type
1 document

Refine by Publication Year
1 2008

1 Search Results for "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