EFFICIENT PARALLEL RECOGNITION ALGORITHMS OF COGRAPHS AND DISTANCE HEREDITARY GRAPHS

Authors
DAHLHAUS E
Citation
E. Dahlhaus, EFFICIENT PARALLEL RECOGNITION ALGORITHMS OF COGRAPHS AND DISTANCE HEREDITARY GRAPHS, Discrete applied mathematics, 57(1), 1995, pp. 29-44
Citations number
32
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
57
Issue
1
Year of publication
1995
Pages
29 - 44
Database
ISI
SICI code
Abstract
A parallel algorithm to recognize cographs with a linear processor bou nd and a log2n time bound is presented. This result extends the result of Adhar and Peng (1990). Moreover, we get a better time processor pr oduct than the algorithm of Lin and Olariu (1991). As a consequence di stance hereditary graphs can be recognized by the same processor and t ime bound.