LOCATING VERTICES OF A STEINER TREE IN AN ARBITRARY METRIC SPACE
LOCATING VERTICES OF A STEINER TREE IN AN ARBITRARY METRIC SPACE
复制标题
DOI：
10.1007/bf01681346
复制
发表时间：
1975-01-01
影响因子：
2.7
通讯作者：
ROUSSEAU, P
中科院分区：
文献类型：
--
作者：
SANKOFF, D;ROUSSEAU, P
给定一棵树，其每个终端顶点与紧度量空间中的一个给定点相关联，问题是将该空间中的一个点与树的每个非终端顶点最优地相关联。最优性准则是在度量空间中，在树的所有边上的长度之和的最小化。本说明显示了如何动态规划解决这个问题的一般化的一些以前发表的算法在不同的度量空间，其中每一个都有直接和重要的应用生物系统学或进化理论。
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.