星图上最短路改进问题的组合算法

摘要：

给定星图中一个非中心点到其余所有非中心点之间的n对点对,当要求网络中边的权重只允许减少且减少量有上界,并且这n对点对的最短路长度都不超过给定的n个上界的条件下,研究了l1模下星图的最短路改进问题,得到了解该问题的强多项式时间的组合算法,算法的时间复杂度为O(| E |log | E |).

关键词：最短路改进问题、l1模、组合算法、强多项式时间算法

所属期刊栏目：22

分类号：TP301;O221(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目11171316;浙江省自然科学基金项目资助Y6090472

在线出版日期：2012-03-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：394-397