A sequential and parallel algorithm for disjoint cliques problem on interval graphs

Sukumar Mondal

Abstract

Using DAG approach,A sequential algorithm is presented to solve disjoint cliques problem on interval graph G which takes O(n^2) time where n is the number of vertices of the graph. For the same problem a O(log2n) time parallel algorithm is presented which takes processors on an EREW PRAM model. Also, on a CREW model it takes O(logn) time with O(n^(3+ε) ),ε>0 processors.