Tree-Realizability of a Distance Matrix

Overview

Objectives/Goals A fast algorithm for both testing the tree-realizability of a distance matrix and constructing the optimal realization is presented. The fastest existing algorithms are only designed to either test tree-realizability or construct a realization. Methods/Materials The presented algorithm's modifications over existing algorithms include a streamlined list of input parameters and maintaining a growing distance matrix. Results In addition to combining both testing and constructing algorithms, the improvements offer several other advantages: early halting upon detecting a non-tree-realizable distance matrix, a running time that is just as fast as existing construction algorithms on input that is realizable, and faster performance for input that is non-tree-realizable. The algorithm has a worst-case running time that is quadratic in the order of the input distance matrix and attains the subquadratic running times that are possible in existing algorithms that only construct the realization. For non-tree-realizable input, the algorithm needs to process, in expectation, at most three-quarters of the vertices to halt. Conclusions/Discussion Tree-realizations can make naturally difficult problems such as the traveling salesman problem more easily solvable optimally over a tree-metric. In addition to its implications in the study of graph theoretic algorithms, the proposed algorithm also has applications in many varied disciplines: phylogenetic tree reconstruction in molecular and evolutionary biology, prediction of physical properties of alkanes in organic chemistry, inference of Internet network topology, evaluation of Internet performance, and the analysis of memory and mental association in psychology.

Awards (1)

• First Place

Competition history

• CSEF 2007 Mathematics & Software · Entry S1302

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2007 project
• CSEF First Place winners