递归集的强多项式时间归结度对的性质

本文研究强多项式时间归结度上半格【TSN;≤T】和【mSN;≤m】的代数性质。证明了对任意给定度,存在度和使得,且,但不存在。籍此上半格【TSN;≤T】和【mSN;≤m】不是格;任意给定的度都是极小对的一半。进一步,我们证明了存在度使得且没有度有性质。

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

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

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位l范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络G=(V,E,w),支撑树T^(0),下界向量l,上界向量u及数值K,寻求一个新的边权向量w满足上下界约束l≤w≤u,且T^(0)是在向量w下权值为K的一个最小支撑树,目标是在单位l范数下使得修改成本‖w-w‖最小。本文给出了该问题的数学模型,分析了其最优性条件,设计了求解该问题的时间复杂度为O(|V||E|)的强多项式时间算法。

环上的最大最小路划分问题

证明了环上的两个最大最小路划分问题是属于P类的,并且给出了两个强多项式时间算法.

求解单位L_(∞)范数下带值约束的最大权完美匹配逆问题的算法

通过研究单位L_(∞)范数下的带值约束的最大权完美匹配逆问题的性质,将单位L_(∞)范数下最大权完美匹配逆问题转化为求解最大平均交替圈问题,给出一个求解该类问题的一个强多项式时间算法,其时间复杂度为O(n^(4)).并通过一个算例,验证了给出的算法的有效性.