Computer Science – Data Structures and Algorithms
Scientific paper
2008-02-20
Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (
Computer Science
Data Structures and Algorithms
Scientific paper
Consider a set of labels $L$ and a set of trees ${\mathcal T} = \{{\mathcal T}^{(1), {\mathcal T}^{(2), ..., {\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.
Hoang Viet Tung
Sung Wing-Kin
No associations
LandOfFree
Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-647940