Abstract: k-edge connectivity augmentation problems in graph theory are bringing to more and more attention along with extensive applications of parallel computing and network technology. Early research has proved that general augmentation problems are NP-hard, but there are polynomial-time sequential algorithms for some subproblems, in which k=2 and weights of all edges in edge set of complement of graph are equal. In this paper a parallel algorithm for above subproblems running in O(log(n)) time and using O(n+m) processors on SIMD PRAM CRCW is presented.

Key words: graph augmentation problems, k-edge connectivity, NC algorithms

摘要： 随着并行计算和网络技术的广泛应用，图论中的k-边连通性增广问题受到越来越多的注意。早期的研究已经证明一般性的增广问题是NP难的，但对它的某些子问题，即当k=2，E₀(G的补图的边集)中所有边的权都相等时，存在着多项式时间的顺序算法。本文针对上述子问题，在SIMD PRAM CRCW并行计算模型上给出了一个O(logn)时间，O(n+m)处理器的NC算法。

关键词: 图增广问题, k-边连通性, NC算法