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

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

AOE网的并行算法

在并行图论算法中,有向图G(V,E)的重要应用之一是边表示活动的网(即AOE网).本文研究AOE网的并行算法.假定AOE网是一个带权的有向无环图,其中顶点i∈V表示事件,有向边∈E表示活动,权w(i,j)表示活动的持续时间.为不失一般性,进一步假定:V={1,2,…,n},起始点s=1,终止点t=n。 本文是在单指令流多数据流(SIMD)机器上研究并行算法.假定机器有一个无限大的共享主存贮器,有f(n)个处理器(其中f(n)是n的多项式),所有处理器可同时读