检索
E-mail
RSS
作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (11): 51-52,55.doi: 10.3969/j.issn.1000-3428.2012.11.016

• 软件技术与数据库 • 上一篇    下一篇

求解区间图K-连接最短路径问题的在线算法

徐云峰，Rudolf Fleischer   

  1. (复旦大学计算机科学技术学院上海市智能信息处理重点实验室，上海 201203)
  • 收稿日期:2012-01-12 出版日期:2012-06-05 发布日期:2012-06-05
  • 作者简介:徐云峰(1987－)，男，硕士研究生，主研方向：图理论，在线与随机算法；Rudolf Fleischer，教授、博士生导师
  • 基金项目:
    国家自然科学基金资助项目(60973026)；上海市重点学科建设基金资助项目(B114)；上海市科委科技基金资助项目(08DZ22 71800)

On-line Algorithm for K-link Shortest Path Problem on Interval Graph

XU Yun-feng, Rudolf Fleischer   

  1. (Shanghai Key Laboratory of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai 201203, China)
  • Received:2012-01-12 Online:2012-06-05 Published:2012-06-05

PDF

1081

摘要： 针对含有n个区间的区间图K-连接最短路径(K-SP)问题，提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质，利用改进的动态规划算法和贪心算法，优化在线算法的时间复杂度。理论分析结果表明，该算法的时间复杂度为O(nK+nlgn)，与目前已知最优的离线算法复杂度相同。

关键词: 区间图, 最短路径问题, K-连接最短路径问题, 贪心算法, 在线算法

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.

Key words: interval graph, shortest path problem, K-link Shortest Path(K-SP) problem, greedy algorithm, on-line algorithm

中图分类号: