网络上的最优干线选择问题

摘要：

考虑在网络上点到路的距离意义下的最优干线选择问题--最小加权距离和问题和最小最大加权距离问题.首先证明所讨论的两个问题的判定形式是NP-完全的,然后对于网络是树的情况,给出了求解问题的算法,该算法的复杂性是O(n2).

关键词：网络选址、点-路距离、算法复杂性、多项式算法

所属期刊栏目：39

分类号：O157.6(代数、数论、组合理论)

在线出版日期：2008-05-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：22-25