基本信息来源于合作网站,原文需代理用户跳转至来源网站获取       
摘要:
针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法.分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度.理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同.
推荐文章
求解k条最短路径问题的混合蛙跳算法
混合蛙跳算法
最短路径
局部搜索
基于k-最短路由的mesh光网络p圈构造方法
网状
光网络
p圈
保护
k-最短路由
圈构造
基于k-臂分子求解最短路径的DNA计算模型
DNA计算
k-臂分子
粘贴模型
最短路径
k最短可靠路径及其优化问题
网络可靠性
k最短可靠路径
子网络
路径优化
优化策略
边失效模型
内容分析
关键词云
关键词热度
相关文献总数  
(/次)
(/年)
文献信息
篇名 求解区间图K-连接最短路径问题的在线算法
来源期刊 计算机工程 学科 工学
关键词 区间图 最短路径问题 K-连接最短路径问题 贪心算法 在线算法
年,卷(期) 2012,(11) 所属期刊栏目 软件技术与数据库
研究方向 页码范围 51-52,55
页数 分类号 TP301.6
字数 3523字 语种 中文
DOI 10.3969/j.issn.1000-3428.2012.11.016
五维指标
作者信息
序号 姓名 单位 发文数 被引次数 H指数 G指数
1 Rudolf Fleischer 复旦大学计算机科学技术学院上海市智能信息处理重点实验室 4 4 1.0 2.0
2 徐云峰 复旦大学计算机科学技术学院上海市智能信息处理重点实验室 1 0 0.0 0.0
传播情况
(/次)
(/年)
引文网络
引文网络
二级参考文献  (13)
共引文献  (87)
参考文献  (5)
节点文献
引证文献  (0)
同被引文献  (0)
二级引证文献  (0)
1954(1)
  • 参考文献(0)
  • 二级参考文献(1)
1975(1)
  • 参考文献(0)
  • 二级参考文献(1)
1979(1)
  • 参考文献(0)
  • 二级参考文献(1)
1980(1)
  • 参考文献(0)
  • 二级参考文献(1)
1989(2)
  • 参考文献(0)
  • 二级参考文献(2)
1992(1)
  • 参考文献(0)
  • 二级参考文献(1)
1994(1)
  • 参考文献(1)
  • 二级参考文献(0)
1997(1)
  • 参考文献(0)
  • 二级参考文献(1)
1998(1)
  • 参考文献(0)
  • 二级参考文献(1)
1999(1)
  • 参考文献(0)
  • 二级参考文献(1)
2000(3)
  • 参考文献(2)
  • 二级参考文献(1)
2007(1)
  • 参考文献(1)
  • 二级参考文献(0)
2008(2)
  • 参考文献(0)
  • 二级参考文献(2)
2009(1)
  • 参考文献(1)
  • 二级参考文献(0)
2012(0)
  • 参考文献(0)
  • 二级参考文献(0)
  • 引证文献(0)
  • 二级引证文献(0)
研究主题发展历程
节点文献
区间图
最短路径问题
K-连接最短路径问题
贪心算法
在线算法
研究起点
研究来源
研究分支
研究去脉
引文网络交叉学科
相关学者/机构
期刊影响力
计算机工程
月刊
1000-3428
31-1289/TP
大16开
上海市桂林路418号
4-310
1975
chi
出版文献量(篇)
31987
总下载数(次)
53
总被引数(次)
317027
  • 期刊分类
  • 期刊(年)
  • 期刊(期)
  • 期刊推荐
论文1v1指导