An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs
Debashis Bera, Tapan K. Pal, Madhumangal Pal · International Journal of Computer Mathematics · 1999
In this paper, a set of intervals is constructed by projecting geometrical representation of permutation graph to find all cutvertices and blocks of a permutation graph. The sequential and parallel algorithms are designed to find all cutvertices and blocks of permutation graphs. The sequential algorithms takes O(n) time and parallel algorithm takes O(log n) time using O(n/log n) processors on an EREW PRAM, where n represents the number of vertices of the graph.