PARALLEL ALGORITHMS FOR COGRAPHS AND PARITY GRAPHS WITH APPLICATIONS

Parity graphs are a natural extension of bipartite graphs, and as a subclass, they include cographs. In this paper it is shown that the recognition problem for cographs, transitive orientation, maximum node weighted clique, minimum node coloring, minimum weight domination set, minimum fill-in, isomorphism for cographs are in the class NC. It is noted that the cograph recognition is central to the recognition problem for parity graphs, and a NC algorithm for parity graph recognition is presented based on this fact. The recognition algorithms require O(log2 n) time and use O(mn) processors, where m and n are the number of edges and vertices in the graph respectively. The model of computation used is the CRCW P-RAM (concurrent read concurrent write parallel RAM), where more than one processor can concurrently read from or write into the same memory location. Writing conflicts are resolved in a non-deterministic fashion, i.e., one processor at random succeeds. © 1990.