点对间加权约束的最小费用连接问题

• 作者: 陈光亭
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 约束最短路 加权约束 多项式时间近似方案
• 年，卷（期）: 2001,（1）
• 页码范围: 1-6
• 页数: 6页
• 语种: 中文
• DOI: 10.3969/j.issn.1001-9146.2001.01.001

摘要

本文首先提出一个有向网络中点对间加权约束的最小费用连接问题.当点对数为1时即为约束最短路问题,因此这是一个NP-C问题.本文设法在原有网络基础上构造出一个新的2维网络,然后利用约束最短路问题的算法给出一个点对数为2时的多项式时间近似方案(PTAS).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈光亭		44	74	5.0	7.0