Title :
An optimal parallel matching algorithm for cographs
Author :
Lin, Rong ; Olariu, Stephan
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Geneseo, NY, USA
Abstract :
The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. The authors show that the problem of finding a maximum matching in a cograph can be solved optimally in parallel by reducing it to parenthesis matching. With a n-vertex cograph G represented by its parse tree as input the algorithm finds a maximum matching in G in O(log n) time using O(n/log n) processors in the EREW-PRAM model
Keywords :
computational complexity; graph theory; parallel algorithms; trees (mathematics); EREW-PRAM model; cographs; complement-reducible graphs; maximum matching; n-vertex cograph; optimal parallel matching algorithm; parenthesis matching; parse tree; Application software; Computer science; Concurrent computing; Mathematics; Parallel algorithms; Parallel processing; Tree graphs;
Conference_Titel :
Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2310-1
DOI :
10.1109/SPDP.1991.218186
