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

• 作者: 刘林
• 来源期刊: 郑州大学学报（理学版）
• 学科: 数学
• 关键词: 网络选址 点-路距离 算法复杂性 多项式算法
• 年，卷（期）: 2007,（4）
• 页码范围: 22-25
• 页数: 4页
• 分类号: O157.6
• 字数: 3718字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-6841.2007.04.005

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘林	郑州航空工业管理学院数理系	22	119	6.0	10.0