Title :
An efficient parallel recognition algorithm of parity graphs
Author_Institution :
Basser Dept. of Comput. Sci., Sydney Univ., NSW, Australia
Abstract :
A parallel algorithm is developed which recognizes parity graphs in O(log2 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)
Keywords :
computational complexity; graph theory; parallel algorithms; parity; pattern recognition; computation theory; linear processor number; parallel algorithm; parity graph recognition algorithm; Bipartite graph; Computer science; Concurrent computing; Databases; Gaussian processes; Operations research; Parallel algorithms; Parallel processing;
Conference_Titel :
Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
Conference_Location :
Sudbury, Ont.
Print_ISBN :
0-8186-4212-2
DOI :
10.1109/ICCI.1993.315399