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的多项式),所有处理器可同时读