A 3-approximation algorithm for the subtree between phylogenies

Simple item page
dc.contributor.authorBordewich, M.
dc.contributor.authorMcCartin, C.
dc.contributor.authorSemple, C.
dc.date.accessioned2016-05-30T21:43:07Z
dc.date.available2016-05-30T21:43:07Z
dc.date.issued2007en
dc.description.abstractIn 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.en
dc.identifier.issn1172-8531
dc.identifier.urihttp://hdl.handle.net/10092/12224
dc.language.isoen
dc.publisherUniversity of Canterburyen
dc.rightsAll Rights Reserveden
dc.rights.urihttps://canterbury.libguides.com/rights/theses
dc.subject.anzsrcFields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematicsen
dc.titleA 3-approximation algorithm for the subtree between phylogeniesen
dc.typeDiscussion / Working Papers
uc.collegeFaculty of Engineering
uc.departmentSchool of Engineeringen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
bordewich_mccartin_semple_ucdms2007-3_report.pdf
Size:
1.89 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Engineering: Reports