Jesper Jansson,
Nguyen Bao Nguyen and
WingKin Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. In SICOMP, Vol. 35(5):10981121, 2006. 1 comment Keywords: approximation, explicit network, from triplets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/triplets_to_gn7_SICOMP2006.pdf.
Toggle abstract
"This paper considers the problem of determining whether a given set Τ of rooted triplets can be merged without conflicts into a galled phylogenetic network and, if so, constructing such a network. When the input Τ is dense, we solve the problem in O(Τ) time, which is optimal since the size of the input is Θ(Τ). In comparison, the previously fastest algorithm for this problem runs in O(Τ2) time. We also develop an optimal O(Τ)time algorithm for enumerating all simple phylogenetic networks leaflabeled by L that are consistent with Τ, where L is the set of leaf labels in Τ, which is used by our main algorithm. Next, we prove that the problem becomes NPhard if extended to nondense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set Τ of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883 ·Τ of the rooted triplets in Τ. On the other hand, we provide a polynomialtime approximation algorithm that always outputs a galled network consistent with at least a factor of 5/12 (> 0.4166) of the rooted triplets in Τ. © 2006 Society for Industrial and Applied Mathematics."
Comments: 
1.  Journal version of JNS2005, improves complexity of JanssonSung2006 
