东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

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

ISSN号：1004-1540
期刊名称：中国计量学院学报
时间：2011
页码：394-397
分类：TP301[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术] O221[理学—运筹学与控制论;理学—数学]
作者机构：[1]中国计量学院理学院,浙江杭州310018, [2]信阳职业技术学院数学与计算机科学学院,河南信阳464000
相关基金：国家自然科学基金资助项目（No.11171316）; 浙江省自然科学基金项目资助（No.Y6090472）
相关项目：网络p-重心选址反问题的复杂性与算法研究

关键词：最短路改进问题, l1模, 组合算法, 强多项式时间算法, shortest path improvement problem, l1 norm, combinatorial algorithm, strongly polynomial time algorithm

中文摘要：

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

英文摘要：

Given n vertex pairs from a non-center vertex to all other non-center vertices in a star graph,we considered the shortest path improvement problem under l1 norm,where the edge weights could only be decreased with the given intervals and the lengths of the shortest paths of the given vertex pairs must satisfy the given bounds.We give a combinatorial algorithm to solve the problem at strongly polynomial time,which runs in O（｜E｜log｜E｜） time.

同期刊论文项目