DocumentCode :
1988812
Title :
An efficient parallel recognition algorithm of parity graphs
Author :
Dahlhaus, Elias
Author_Institution :
Basser Dept. of Comput. Sci., Sydney Univ., NSW, Australia
fYear :
1993
fDate :
27-29 May 1993
Firstpage :
82
Lastpage :
86
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
Conference_Location :
Sudbury, Ont.
Print_ISBN :
0-8186-4212-2
Type :
conf
DOI :
10.1109/ICCI.1993.315399
Filename :
315399
Link To Document :
بازگشت