10.3969/j.issn.1000-3428.2012.11.016
求解区间图K-连接最短路径问题的在线算法
针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法.分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度.理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同.
区间图、最短路径问题、K-连接最短路径问题、贪心算法、在线算法
38
TP301.6(计算技术、计算机技术)
国家自然科学基金资助项目60973026;上海市重点学科建设基金资助项目B114;上海市科委科技基金资助项目08DZ2271800
2012-09-29(万方平台首次上网日期,不代表论文的发表时间)
共3页
51-52,55