An efficient parallel recognition algorithm of parity graphs
Elias Dahlhaus · 2002
A parallel algorithm is developed which recognizes parity graphs in O(log/sup 2/ n) time using a linear number of processors. This improves previous results of G. Adhar and S. Peng (J. Algorithms, vol. 11, pp. 252-284, 1990) and of T. Przytycka and D. Corneil (J. Algorithms, vol. 12, pp. 96-109, 1991).>