Acta scientiarum naturalium Universitatis Pekinensis
QU Wanling, YUAN Chongyi
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.
QU Wanling,YUAN Chongyi. A NC Algorithm for Graph Augmentation Problems[J].Acta scientiarum naturalium Universitatis Pekinensis, 1998, 34(5): 696-699.
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks