期刊文献+
共找到1篇文章
< 1 >
每页显示 20 50 100
求解区间图K-连接最短路径问题的在线算法
1
作者 徐云峰 Rudolf Fleischer 《计算机工程》 CAS CSCD 2012年第11期51-52,55,共3页
针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度。理论分析结果表明,该算法的时间复杂度... 针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度。理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同。 展开更多
关键词 区间图 最短路径问题 K-连接最短路径问题 贪心算法 在线算法
下载PDF
上一页 1 下一页 到第
使用帮助 返回顶部