A 3-approximation algorithm for the subtree between phylogenies
Type of content
Discussion / Working Papers
UC permalink
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
University of Canterbury
Journal Title
Journal ISSN
Volume Title
Language
Date
2007
Authors
Bordewich, M.
McCartin, C.
Semple, C.
Abstract
In this paper, we give a (polynomial-time) 3-approximation algorithm for the rooted subtree prune and regraft distance between two phylogenetic trees. This problem is known to be NP-complete and the best previously known approximation algorithm is a 5-approximation. We also give a faster fixed-parameter algorithm for the rooted subtree prune and regraft distance than was previously known.
Description
Citation
Keywords
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Fields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematics
Rights
All Rights Reserved