摘要
随着并行计算和网络技术的广泛应用，图论中的ｋ－边连通性增广问题受到越来越多的注意。早期的研究已经证明一般性的增广问题是ＮＰ难的，但对它的某些子问题，即当ｋ＝２，Ｅ０（Ｇ的补图的边集）中所有边的权都相等时，存在着多项式时间的顺序算法。本文针对上述子问题，在ＳＩＭＤＰＲＡＭＣＲＣＷ并行计算模型上给出了一个Ｏ（ｌｏｇｎ）时间，Ｏ（ｎ＋ｍ）处理器的ＮＣ算法。
kedge 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 NPhard,but there are polynomialtime 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(logn) time and using O(n+m) processors on SIMD PRAM CRCW is presented.
出处
《北京大学学报（自然科学版）》
CAS
CSCD
北大核心
1998年第5期694-699,共6页
Acta Scientiarum Naturalium Universitatis Pekinensis
基金
国家自然科学基金
北大预研基金
攀登计划
关键词
图增广问题
k-边连通性
NC算法
graph augmentation problems
kedge connectivity
NC algorithms
