| 求解区间图K-连接最短路径问题的在线算法 |
| |
| 引用本文： | 徐云峰,Rudolf Fleischer. 求解区间图K-连接最短路径问题的在线算法[J]. 计算机工程, 2012, 38(11): 51-52,55 |
| |
| 作者姓名： | 徐云峰 Rudolf Fleischer |
| |
| 作者单位： | 复旦大学计算机科学技术学院上海市智能信息处理重点实验室,上海,201203 |
| |
| 基金项目： | 国家自然科学基金资助项目，上海市重点学科建设基金资助项目，上海市科委科技基金资助项目 |
| |
| 摘 要： | 针对含有n个区间的区间图K-连接最短路径(K-SP)问题，提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质，利用改进的动态规划算法和贪心算法，优化在线算法的时间复杂度。理论分析结果表明，该算法的时间复杂度为O(nK+nlgn)，与目前已知最优的离线算法复杂度相同。
|
| 关 键 词： | 区间图 最短路径问题 K-连接最短路径问题 贪心算法 在线算法 |
| 收稿时间： | 2012-01-12 |
On-line Algorithm for K-link Shortest Path Problem on Interval Graph |
| |
| XU Yun-feng , Rudolf Fleischer. On-line Algorithm for K-link Shortest Path Problem on Interval Graph[J]. Computer Engineering, 2012, 38(11): 51-52,55 |
| |
| Authors: | XU Yun-feng Rudolf Fleischer |
| |
| Affiliation: | XU Yun-feng,Rudolf Fleischer(Shanghai Key Laboratory of Intelligent Information Processing,School of Computer Science,Fudan University,Shanghai 201203,China) |
| |
| Abstract: | Aiming at K-link Shortest Path(K-SP) problem on n intervals,this paper presents the on-line algorithm for K-SP problem on interval graphs.It studies the properties about interval graphs and the shortest path problem on interval graphs,is based on the intuition of dynamic programming and greedy algorithms to optimize on-line algorithm complexity.Theoretical analysis result shows the complexity of this algorithms is O(nK+nlgn),same as the best off-line algorithm for this problem. |
| |
| Keywords: | interval graph shortest path problem K-link Shortest Path(K-SP) problem greedy algorithm on-line algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载免费的PDF全文 |
