PARALLEL RECOGNITION ALGORITHMS FOR GRAPHS WITH RESTRICTED NEIGHBOURHOODS
Sergio De Agostino, Rossella Petreschi · International Journal of Foundations of Computer Science · 1990
In this paper three parallel recognition algorithms for threshold, matrogenic and box-threshold graphs, respectively, are given. These classes of graphs are inclusionwise comparable and depend only on their degree sequences. The algorithms run in O(log n) parallel time on a PRAM-EREW model of computation and require O(n/log n) processors when the degree sequence, ordered in decreasing fashion, is given as input.