License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1357
URN: urn:nbn:de:0030-drops-13579
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1357/
Go to the corresponding Portal


Hoang, Viet Tung ; Sung, Wing-Kin

Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees

pdf-format:
Document 1.pdf (198 KB)


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.

BibTeX - Entry

@InProceedings{hoang_et_al:LIPIcs:2008:1357,
  author =	{Viet Tung Hoang and Wing-Kin Sung},
  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 =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1357},
  URN =		{urn:nbn:de:0030-drops-13579},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1357},
  annote =	{Keywords: Maximum agreement supertree, maximum compatible supertree}
}

Keywords: Maximum agreement supertree, maximum compatible supertree
Seminar: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI