Parallel algorithm for optimum vertex-rankings of permulation graphs

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.