Approximation Algorithms for Maximum Agreement Forest on Multiple Trees
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
Given a collection of phylogenetic trees with identical leaf label-set, the Maximum Agreement Forest problem (maf) asks for a largest common subforest of these input trees. The maf problem on two binary phylogenetic trees has been studied extensively in the literature. In this paper, we will be focused on the maf problem on multiple (i.e., two or more) binary phylogenetic trees and present two polynomial-time approximation algorithms, one for the maf problem on multiple rooted trees, and the other for the maf problem on multiple unrooted trees. The ratio of our algorithm for the maf problem on multiple rooted trees is 3, which is an improvement over the previously best ratio 8 for the problem. Our 4-approximation algorithm for the maf problem on multiple unrooted trees is the first approximation algorithm for the problem. 2014 Springer International Publishing Switzerland.
name of conference
Computing and Combinatorics - 20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings