An improved parallel algorithm for maximal matching (Q1073571): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 00:32, 31 January 2024

scientific article
Language Label Description Also known as
English
An improved parallel algorithm for maximal matching
scientific article

    Statements

    An improved parallel algorithm for maximal matching (English)
    0 references
    0 references
    0 references
    1986
    0 references
    A parallel \(O(\log^ 3| E|)\) algorithm for finding a maximal matching in a graph G(V,E) is presented. The model of computation is the CRCW-PRAM, and \(| V| +| E|\) processors are used. This algorithm is a substantial improvement upon the two previous algorithms known to us. These algorithms by \textit{R. M. Karp} and \textit{W. Wigderson} [Proc. 16th Ann. ACM Symp. Theory of Computing, 266-272 (1984)] and \textit{G. Lev} [''Size bounds and parallel algorithms for networks'', Tech. Rep. CST-8-80, Dept. Comput. Sci., Univ. Edinburgh (1980)] achieve \(O(\log^ 4| E|)\) depth with \(| E|^ 3/\log | E|\) and \(| E| +| V|\) processors respectively. The last one though having a better performance than the first, only applies to bipartite graphs.
    0 references
    parallel computation
    0 references
    CRCW-PRAM
    0 references

    Identifiers