Efficient parallel recognition algorithms of cographs and distance hereditary graphs Original Research Article

A parallel algorithm to recognize cographs with a linear processor bound and a log2n time bound is presented. This result extends the result of Adhar and Peng (1990). Moreover, we get a better time processor product than the algorithm of Lin and Olariu (1991). As a consequence distance hereditary graphs can be recognized by the same processor and time bound.