An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs

Abstract

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.

Keywords:

• Permutation graph
• cut vertex
• block
• design of algorithms
• analysis of algorithms

C.R. Categories:

• E1
• F2
• G2.2
• I1.2