限制性最短路问题

• 作者: 李睿 杨子兰
• 来源期刊: 计算机与信息技术
• 学科: 数学
• 关键词: 限制性最短路 放缩取整法 区间划分法
• 年，卷（期）: jsjyxxjs,（2）
• 页码范围: 24-26
• 页数: 3页
• 分类号: O157.5

摘要

给定一个无圈图G及与边关联的长度权重和时间权重,需要寻找G上固定两点之间的关于长度权重的最短路,并且路上关于时间权重的路长不能超过给定的一个正常数。这就是限制性最短路问题。本文给出了限制性最短路问题的几种FPTAS,并对算法的复杂度进行了分析,对算法的一些部分进行改进,最后把算法推广到一类有圈的图上。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李睿	云南大学旅游文化学院信息与计算机科学系	17	9	2.0	2.0
2	杨子兰	云南大学旅游文化学院信息与计算机科学系	14	8	2.0	2.0