hide
Free keywords:
Mathematics, Combinatorics, math.CO,Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
Choi et. al (2011) introduced a minimum spanning tree (MST)-based method
called CLGrouping, for constructing tree-structured probabilistic graphical
models, a statistical framework that is commonly used for inferring
phylogenetic trees. While CLGrouping works correctly if there is a unique MST,
we observe an indeterminacy in the method in the case that there are multiple
MSTs. In this work we remove this indeterminacy by introducing so-called
vertex-ranked MSTs. We note that the effectiveness of CLGrouping is inversely
related to the number of leaves in the MST. This motivates the problem of
finding a vertex-ranked MST with the minimum number of leaves (MLVRMST). We
provide a polynomial time algorithm for the MLVRMST problem, and prove its
correctness for graphs whose edges are weighted with tree-additive distances.
