Title :
Simple randomized parallel algorithms for finding a maximal matching in an undirected graph
Author :
Yang, S.B. ; Dhall, S.K. ; Lakshmivarahan, S.
Author_Institution :
Sch. of Electr. Eng. & Comput. Sci., Oklahoma Univ., Norman, OK, USA
Abstract :
The authors present simple randomized parallel algorithms for finding a maximal matching in a unidirectional graph G=(V , E) for the CRCW and CREW models. The algorithm for the CRCW model has O(log m) expected running time using m processors, where m is the number of edges in G . It is also shown that the CRCW algorithm can be implemented on a CREW PRAM (parallel random access machine). The CREW algorithm runs in O(log2 m) time, but it requires only m /log m processors
Keywords :
computational complexity; graph theory; parallel algorithms; CRCW algorithm; CREW PRAM; CREW algorithm; edges; expected running time; maximal matching; parallel random access machine; randomized parallel algorithms; undirected graph; unidirectional graph; Computer science; Parallel algorithms; Phase change random access memory; Terminology;
Conference_Titel :
Southeastcon '91., IEEE Proceedings of
Conference_Location :
Williamsburg, VA
Print_ISBN :
0-7803-0033-5
DOI :
10.1109/SECON.1991.147821
