-
题名星图上最短路改进问题的组合算法
- 1
-
-
作者
台伟英
湛宁
王勤
-
机构
中国计量学院理学院
信阳职业技术学院数学与计算机科学学院
-
出处
《中国计量学院学报》
2011年第4期394-397,共4页
-
基金
国家自然科学基金资助项目(No.11171316)
浙江省自然科学基金项目资助(No.Y6090472)
-
文摘
给定星图中一个非中心点到其余所有非中心点之间的n对点对,当要求网络中边的权重只允许减少且减少量有上界,并且这n对点对的最短路长度都不超过给定的n个上界的条件下,研究了l1模下星图的最短路改进问题,得到了解该问题的强多项式时间的组合算法,算法的时间复杂度为O(|E|log|E|).
-
关键词
最短路改进问题
l1模
组合算法
强多项式时间算法
-
Keywords
shortest path improvement problem
l1 norm
combinatorial algorithm
strongly polynomial time algorithm
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
O221
[理学—运筹学与控制论]
-
-
题名单位无穷范数下边权有界的最小支撑树逆最优值问题
被引量：1
- 2
-
-
作者
张斌武
关秀翠
-
机构
河海大学理学院
东南大学数学学院
-
出处
《运筹学学报》
CSCD
北大核心
2022年第3期44-56,共13页
-
基金
国家自然科学基金(No.11471073)。
-
文摘
研究了单位l范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络G=(V,E,w),支撑树T^(0),下界向量l,上界向量u及数值K,寻求一个新的边权向量w满足上下界约束l≤w≤u,且T^(0)是在向量w下权值为K的一个最小支撑树,目标是在单位l范数下使得修改成本‖w-w‖最小。本文给出了该问题的数学模型,分析了其最优性条件,设计了求解该问题的时间复杂度为O(|V||E|)的强多项式时间算法。
-
关键词
最小支撑树
l_(∞)范数
逆最优值问题
强多项式时间算法
-
Keywords
minimum spanning tree
l_(∞) norm
inverse optimal value problem
strongly polynomial time algorithm
-
分类号
O221.2
[理学—运筹学与控制论]
-
-
题名环上的最大最小路划分问题
被引量：1
- 3
-
-
作者
陈嘉明
-
机构
玉溪农业职业技术学院
-
出处
《甘肃联合大学学报（自然科学版）》
2011年第5期17-18,共2页
-
文摘
证明了环上的两个最大最小路划分问题是属于P类的,并且给出了两个强多项式时间算法.
-
关键词
最大最小路划分
运行时间
强多项式时间算法
-
Keywords
max-min path partition
running time
strong polynomial-time algorithm
-
分类号
O15
[理学—基础数学]
-
