所有点对之间最快路问题

所有点对之间最快路问题就是要在所有点对(Vs，Vt)之间传送数据δs,t,并找出一条最快的路线．解决所有点对之间最快路问题的关键是产生有效解的等价集合．运用动态点对最短路的算法，本文首先设计了一个时间复杂性为O(mn^2)的产生有效解等价集合的算法，然后研究了静态点对之间最快路问题和动态点对之间最快路问题，其算法的时间复杂性分别为O(mn^2)和O(m^2n^2)．最后本文研究了求和对最小的路问题，证明该问题可以在O(mn^2)时间内解决．     

有向循环图强连通度的下界

为简便计,本文采用文[1]中的定义和符号,而未说明的概念或符号引自[3].本文仅讨论有限、简单有向图. 有向图D=(V,A)称为强连通的,如果对D的任两顶点u与v,在D中同时存在(u,v)—有向路和(v,u)—有向路,C(?)V称为D的点割集,如果D—C非强连通或是单点.D的所含点数最少的点割集称为最小点割集,其阶数定义为D的强连通度,记为k(D)或k. 循环有向图D(n,S)定义如下:     

Dijkstra算法的一个改进

本文得到了一种Dijkstra算法的改进算法，如果最短路问题具有n个点和m条边，那么改进算法把问题的计算复杂性从原来的O(nlogn m)降低为O(nlogn M)(M≤m)。     

关于最短路问题的一个双目标优化问题

本文研究了一个双目标最短路问题的变形问题,在该变形问题中,一个目标函数还是路的长度,另一个目标函数则是路的容量,在Pareto-optimal最优解的意义下,本文给出了一个时间复杂性为O（n^3 )的算法,在字典序最优解的意义下,本文给出了一个时间复杂性为O(n^3)的算法。     

新的素数检测方法

提出了一个快速而简单的素数检测方法,它的时间复杂性为O(log^(3+ε)N)这里0<ε≤1,空间复杂性为O(logN),N≡3(mod 4)时,时间复杂性为O(log(3+ε)N)这里0<ε≤1,空间复杂性为O(logN),N≡3(mod 4)时,时间复杂性为O(log^(2+ε)N),是迄今为止最快的多项式算法.     

弦图子类的全控制函数

本文首先证明了k-全控制问题和符号全控制问题在双弦图上均为NP-完全的.其次,在强消去序已给定的强弦图上,给出了求解符号全控制、负全控制、k-全控制和k-全控制问题的统一的O(m+n)时间算法.     

非平衡分派问题的次数序列算法

根据 [2 ]中的结论 ,得到一个利用顶点的次数向量求解非平衡分派问题的算法 ,该算法不受退化解的影响 ,且其复杂性为 O(n· m3 ) .     

航空器供油问题中完全逆序类中的多项式时间可解类

航空器供油问题是一类非线性组合优化问题,其目标函数为分式形式,该问题目前不存在多项式时间算法,也未被证明是NP完全问题。一般可以用置换来刻画n架飞机的一个供油顺序。该问题中有一类实例被称为“完全逆序类”,“完全逆序类”用动态规划算法求解计算时间为O(n2ⁿ),具有指数时间复杂度。本文通过对该“完全逆序类”问题做进一步分析,发现在“完全逆序类”中也存在着多项式时间可解的情况。定理1研究一类一次可解的情况,若问题满足定理1的条件,则求解一次即可找到其最优解;定理2研究一类多项式时间可解的情况,当问题满足定理2的条件时,其最优解可在多项式时间内获得。     

单机两组工件继列分批与平行分批混合排序

研究单机两组工件继列分批与平行分批混合排序.在问题中有两组工件J^A和JA和J^B.A-工件可以在平行批中进行加工,B-工件可以在继列批中进行加工.对若干正则目标函数给出了多项式时间算法.主要结果如下:·排序问题1|s-p-batch,s(B),(∞,∞)|L_(max)在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,s(B),(∞,b(B))|∑C_j在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,p_j=1,s(B),(b(A),b(B))|∑w_jC_j在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,s(B),(∞,b(B))|f_(max)可以在时间界为O(log(max_jf_j(M))×(nlogM+n_An_Bn))内可解.其中,M是工件完工时间的一个上界.     

工件间具有串并有向图约束的单机随机排序问题

研究机器发生随机故障的单机排序问题,其中工件间的优先约束为串并有向图,目标函数为极小化加权完工时间和,证明了此问题多项式时间可解,并给出了多项式时间算法.     

关于区间图的一些有效并行算法

本文基于SIMD-CREW-PRAM一种可同时读但不可同时写的共享计算模型,给出了有关区间图的一些有效的并行算法。如找最大加权集团,最小集团覆盖,等权区间图的最大独立集及最小支配集,真区间图的哈密顿回路及最小带宽。所有这些算法都是最优的,其时间复杂性为O(logn)和处理器数为O(n)。     

最小顶点覆盖问题的加权分治算法

最小顶点覆盖问题是组合优化中经典NP-Hard问题之一,其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术,该技术主要用于对分支降阶的递归算法进行复杂性分析,其核心思想可以理解为依据问题不同的特征设置一组相应的权值,以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题,并通过加权分治技术分析得出该算法的时间复杂度为O(1.255ⁿ),优于常规分析下的时间复杂度O(1.325ⁿ) 。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。     

关于有限群、环、域的判定算法

给定n元集合上的一个二元运算的乘法表(共n~2项)。判定它是不是群,过去的算法需时O(n~3)。我们给出了一个O(n~2)时间的算法。对于环和域的判定,我们也给出了O(n~2)时间的算法。这些算法的时间复杂性的阶已经不能再改进了。     

一个求解P_*(k)阵线性互补问题的渐近O((k 1)n~3L)宽域路径跟踪算法

本文通过使用高界校正技术，给出了一个求解P*(k)阵线性互补问题的宽域路径跟踪算法，其迭代复杂性为渐近O((k＋1)L)．通过使用秩-1校正技术，其每步的计算复杂性从常规的O(n3)约减到O(n2.5)；因此，算法总的计算复杂性为渐近O((k＋1)n3L)．     

分支数≤7时S^2NS有向图的禁用子图刻划

实方阵A称为强符号非异阵（S~2NS阵）,若任一与A符号模式相同的矩阵非异且其逆的符号模式也一致。若一个有向图是某一S~2NS阵对应赋号有向图的基础有向图,称为S~2NS有向图。本文用禁用子图形式给出了分支数≤7时有向图成为S~2NS有向图的刻划,同时部分地解决了[2]和[4]中提出的问题。     

一个约束乘积最大问题的强多项式时间算法

本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为O(n2)的强多项式时间算法,并且对于单边约束的情形给出了复杂度更低(O(nlnn))的强多项式时间算法.     

强连通双圈有向图的无符号拉普拉斯谱刻画

设$\overrightarrow{G}$ 是一个强连通双圈有向图, $A(\overrightarrow{G})$是其邻接矩阵.设$D(\overrightarrow{G})$ 是$\overrightarrow{G}$的顶点出度的对角矩阵, $Q(\overrightarrow{G})=D(\overrightarrow{G})+A(\overrightarrow{G})$是$\overrightarrow{G}$ 的无符号拉普拉斯矩阵. $Q(\overrightarrow{G})$的谱半径称为$\overrightarrow{G}$的无符号拉普拉斯谱半径.在这篇文章中, 确定了在所有强连通双圈有向图中达到最大或最小无符号拉普拉斯谱半径的唯一有向图. 此外,还证明了任意一个强连通双圈有向图是由它的无符号拉普拉斯谱所确定的.     

具有限制的最小 k一个边不交支撑树问题

本文推广了刘振宏等具有次限制最小树算法,给出了求具有限制的最小 k 个边不交支撑树算法.该算法已在 IBM-PC 机上用 Fortran 语言实现,其时间复杂性为max{O(k~2|E|~2|V|~2),O(k~3|V|~4|E|)}.     

一种新的可分凸二次规划的不可行内点算法

本文对可分凸二次规划提出了一个新的不可行内点算法 ,证明了该算法是一个多项式时间算法 ,并将迭代复杂性界降至O(nL) .     

最小平均长度回路问题的一个有效算法

本文提出了求解最小平均长度回路问题的一个有效算法。从本质上来说,这一算法是原始——对偶算法。该算法通过反复求解一系列织合特点更强的子问题,从而有效地求得最优解。我们还证明了算法的复杂性为 O(n~4),并且通过计算大量随机产生的实例并与已有算比较,证明该算法是很有效的。