树结构与更新最小生成树的并行算法

摘要

更新最小生成树问题,即已知图的最小生成树,当图的某条边的赋值被改变,如何快速有效的求新出的最小生成树.本文引进了∑-树结构,并以此获得了一个快速有效的更新最小生成树的并行算法,并行时间为O(logn),处理器个数为O(n^(4/(?)),计算模型为CREW-PRAM.其中n 为图的顶点个数,而且,进行预处理所需的时问也只需O(log^2n),处理器个数为O(n^(?)),存贮数据所需的空间为O(n^(?)).