TY - GEN
T1 - Simple randomized parallel algorithms for finding a maximal matching in an undirected graph
AU - Yang, S. B.
AU - Dhall, S. K.
AU - Lakshmivarahan, S.
PY - 1991
Y1 - 1991
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0025798262&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025798262&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0025798262
SN - 0780300335
T3 - Conference Proceedings - IEEE SOUTHEASTCON
SP - 579
EP - 581
BT - Conference Proceedings - IEEE SOUTHEASTCON
PB - Publ by IEEE
T2 - IEEE Proceedings of the SOUTHEASTCON '91
Y2 - 8 April 1991 through 10 April 1991
ER -