在赋权 l1模和 l∞模下树上的2-重心选址改进问题

• 作者: 关秀翠 杨利平
• 来源期刊: 东南大学学报（英文版）
• 学科: 数学
• 关键词: 2-重心 网络改进问题 树 背包问题 l1 模 l∞模
• 年，卷（期）: 2013,（3）
• 页码范围: 346-351
• 页数: 6页
• 分类号: O224
• 字数: 1225字
• 语种: 英文
• DOI: 10.3969/j.issn.1003-7985.2013.03.021

摘要

研究了在树网络上的2-重心选址改进问题，该问题是指以最少的花费调整各边的权值使得修改后网络中所有顶点到2个预设点的赋权距离的和不超过给定的上界。采用l1模和l∞模衡量总的修改花费。这2类问题具有较强的实际应用价值与理论研究价值。这2类改进问题可分别等价地转化为一系列的和型及瓶颈型的连续背包问题，基于最优解的特性，提出了时间复杂度为O（ n2）的算法来求解这2类问题，其中n是树上顶点的个数。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨利平	东南大学数学系	1	1	1.0	1.0
2	关秀翠	东南大学数学系	5	9	2.0	3.0