ISSN 1002-1027  CN 11-2952/G2

Acta scientiarum naturalium Universitatis Pekinensis

Previous Articles     Next Articles

A NC Algorithm for Graph Augmentation Problems

QU Wanling, YUAN Chongyi   

  1. Department of Computer Science, Peking University, Beijing, 100871
  • Received:1997-06-23 Online:1998-09-20 Published:1998-09-20

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.