Abstract:
In this thesis, we give a parallel algorithm to find the c-vertex-ranking of a permutation
graph. A c-vertex-ranking of a graphG = (V,E), for a positive integer c, is a labeling of
the vertices of G such that, for any label k, deletion of all vertices with labels greater than
k leaves connected components, each having at most c vertices with label k. A c-vertexranking
is optimal if the number of labels used is as small as possible. The c-vertexranking
problem is to find an optimal c-vertex-ranking of a given graph. A graph
G = (V, E) is a permutation graph if V = {I, 2, ... , n} and E = {(i,j) I (i - j)*( Ir-1(i) -
1r-
1(;» < A}, where Ir= (n(I), n(2), ... , n(n)] is a permutation of the numbers 1,2, ... , n
and Ir -1 (i) is the position of i in the permutation. Deogun et al. gave a sequential
algorithm to solve the optimal I-vertex-ranking problem on permutation graphs using
time O(n6
), where n is the number of vertices in the graph. Later, we have solved the
same problem in O(n3) sequential time. But, there is no known patallel algorithm to solve
the c-vertex-ranking problem for permutation graphs. In this thesis, we have devised a
parallel algorithm for the same problem with any value of c that runs in O(log2n) parallel
time using O(n310gn) operations on the CREW PRAM model.
