EFFICIENT PARALLEL ALGORITHMS ON PROPER CIRCULAR-ARC GRAPHS

Efficient parallel algorithms for several problems on proper circular are graphs are presented in this paper. These problems include finding a maximum matching, partitioning into a minimum number of induced sub graphs each of which has a Hamiltonian cycle (path), partitioning into induced subgraphs each of which has a Hamiltonian cycle (path) with a t least k vertices for a given k, and adding a minimum number of edges to make the graph contain a Hamiltonian cycle (path). It is shown her e that the above problems can all be solved in logarithmic time with a linear number of EREW PRAM processors, or in constant time with a lin ear number of BSR processors. A more important part of this work is pe rhaps the extension of basic BSR to allow simultaneous multiple BROADC AST instructions.