We present efficient parallel algorithms for recognizing chordal graphs and locating all maximal cliques of a chordal graph G=(V,E). Our techniques are based on partitioning the vertex set V using information contained in the distance matrix of the graph. We use these properties to formulate parallel algorithms which, given a graph G=(V,E) and its adjacency-level sets, decide whether or not G is a chordal graph, and, if so, locate all maximal cliques of the graph in time 0(k) by using 62»n2/k processors on a CRCW-PRAM, where δ is the maximum degree of a vertex in G and 1 <k<n. The construction of the adjacency-level sets can be done by computing first the distance matrix of the graph, in time O(logn) with 0(nP+DG) processors, where DG is the output size of the partitions and β=2.376, and then extracting all necessary set information. Hence, the overall time and processor complexity of both algorithms are CXlogn) and 0(max{62*n2/Zogn, nP+D0}), respectively. These results imply that, for 6<VnZogn, the proposed algorithms improve in performance upon the best-known algorithms for these problems.
(EN)
University of Ioannina
