Locating the vertices of a steiner tree in an arbitrary metric space |
| |
Authors: | David Sankoff Pascale Rousseau |
| |
Institution: | 1. Université de Montréal, Montréal, Canada
|
| |
Abstract: | Given a tree each of whose terminal vertices is associated with a given point in a compact metric space, the problem is to optimally associate a point in this space to each nonterminal vertex of the tree. The optimality criterion is the minimization of the sum of the lengths, in the metric space, over all edges of the tree. This note shows how a dynamic programming solution to this problem generalizes a number of previously published algorithms in diverse metric spaces, each of which has direct and significant applications to biological systematics or evolutionary theory. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|