## 4 Algorithms and Experimental Results
### FastTree  
The first heuristic algorithm has a bottom-up greedy approach, which is faster than the other previously known algorithms employing a simple data structure. Let _R(T)_ denote the set of all triplets consistent with a given tree, _T. R(T)_ is called the _reflective triplet set_ of \(T\). It forms a minimally dense triplet set and represents \(T\) uniquely [17]. Now, we define the _closeness_ of the pair, {_i,j_}. The closeness of the pair, {_i,j_}, \(C_{i,j}\), is defined as the number of triplets of the form, _ij_|_k_, in a triplet set. Clearly, for any arbitrary tree, \(T\), the closeness of a cherry species equals \(n-2\), which is maximum in _R(T)_. The reason is that every cherry species has a triplet with every other species. Now, suppose we contract every cherry species of the form, {_ij_}, to their parents, \(p_{ij}\), and then update _R(T)_ as follows. For each contracted cherry species, {_i,j_}, we remove triplets of the form, _ij_|_k_, from _R(T)_ and replace \(i\) and \(j\) with \(p_{ij}\) within the remaining triplets. The updated set, \(R^{\prime}(T^{\prime})\), would be the reflective triplet set for the new tree, \(T^{\prime}\). Observe that, for cherries of the form, {\(p_{ij},k\)}, in \(T^{\prime}\), \(C_{i,k}\) and \(C_{j,k}\) would equal n-3 in _R(T)_. Similarly, for cherries of the form, {\(p_{ij},p_{kl}\)}, in \(T^{\prime}\), \(C_{i,k}\), \(C_{j,k}\), \(C_{i,l}\) and \(C_{j,l}\) would equal n-4 in _R(T)_. This forms the main idea of the first heuristic algorithm. We first compute the closeness of pairs of species by visiting triplets. Furthermore, sorting the pairs according to their closeness gives us the reconstruction order of the tree. This routine outputs the unique tree, \(T\), for any given reflective triplet set, _R(T)_. Yet, we have to consider that the input triplet set is not always a reflective triplet set. Consequently, the reconstruction order produced by sorting may not be the right order. However, if the loss of triplets admits a uniform distribution, it will not affect the reconstruction order. An approximate solution for this problem is refining the closeness. This can be done by reducing the closeness of the pairs, {_i,k_} and {_j,k_}, for any visited triplet of the form, _ij_}_k_. Thus, if the pair, {_i,j_}, is actually cherries, then the probability of choosing the pairs, {_i,k_} or {_j,k_}, before choosing the pair, {_i,j_}, due to triplet loss, will be reduced. We call this algorithm FastTree. See Algorithm 1 for the whole algorithm. ```
1:Initialize a forest, \(F\), consisting of \(n\) one-node trees labeled by species. 2:for each triplet of the form _ij_}_k_do
3:\(C_{i,j}\): = \(C_{i,j}\)+1
4:\(C_{i,k}\): = \(C_{i,k}\)\(-\)1
5:\(C_{j,k}\): = \(C_{j,k}\)\(-\)1
6:endfor
7:Create a list, \(L\), of pairs of species. 8:Sort L according to the refined closeness of pairs with a linear-time sorting algorithm. 9:while \(|L|\)\(>\)0 do
10: Remove the pair, {_i,j_}, with maximum, \(C_{i,j}\). 11:if \(i\) and \(j\) are not in the same tree then
12: Add a new node and connect it to roots of trees containing \(i\) and \(j\). 13:endif
14:endwhile
15:if \(F\) has more than one tree then
16: Merge trees in any order, until there would be only one tree. 17:endif
18:return the tree in \(F\)
```  
**Algorithm 1** FastTree  
**Theorem 1**. : _FastTree runs in \(O(m+\alpha(n)n^{2})\) time._  
Proof. : Initializing a forest in Step 1 takes \(O(n)\) time. Steps 2-6 take \(O(m)\) time. We know that the closeness is an integer value between \(0\) and \(n-2\). Thus, we can employ a linear-time sorting algorithm [18]. There are \(O(n^{2})\) possible pairs; therefore, Step 8 takes \(O(n^{2})\) time. Similarly, the while loop in Step 9 takes \(O(n^{2})\) time. Each removal in Step 10 can be done in \(O(1)\) time.