The triangles method to build \(X\)-trees from incomplete distance matrices (Q2773174)

The main result of this paper is a method of time complexity \(O(n^3)\) to infer valued trees having \(X\) as set of leaves from incomplete distance arrays. It allows the building of an unrooted tree using only \(2n-3\) distance values between the \(n\) elements of \(X\), if they fulfill some explicit conditions and it is based upon a weighted generalized 2-tree spanning \(X\), called twotree, which is a 2-connected graph of order \(n\) and size \(n-3\). Also, a method allowing one to recover an \(X\)-tree from a reduced set of pairwise distances between taxa and a greedy algorithm for the construction of a twotree which is an analogue of Prim's algorithm for the shortest spanning tree are proposed.