License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
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://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1357/
Go to the corresponding LIPIcs Volume Portal

Hoang, Viet Tung ; Sung, Wing-Kin

Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees

pdf-format:
22011.HoangVietTung.Paper.1357.pdf (0.2 MB)

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 =		{10.4230/LIPIcs.STACS.2008.1357},
  annote =	{Keywords: Maximum agreement supertree, maximum compatible supertree}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI