We use cookies to improve your experience with our site.
MA Jun, MA Shaohan. An Efficient Parallel Graph Edge Matching Algorithmand Its Applications[J]. Journal of Computer Science and Technology, 1999, 14(2): 153-158.
Citation: MA Jun, MA Shaohan. An Efficient Parallel Graph Edge Matching Algorithmand Its Applications[J]. Journal of Computer Science and Technology, 1999, 14(2): 153-158.

An Efficient Parallel Graph Edge Matching Algorithmand Its Applications

  • A fast and efficient parallel algorithm for finding a maximal edge matching in an undirected graph G(V,E) is proposed. It runs in O(logn) time with O(m/log+n+n) processors on an EREW PRAM for a class of graph set Ⅱ, where n=V, m = E and Ⅱ includes at leut (i) planar graphs; (ii) graphs of bounded genus; and (iii) graphs of bounded maximum degree and so on. Our algorithm improves the previoualy known best algoritbms by a factor of logn in the time complexity…
  • loading

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return