• DocumentCode
    3256387
  • Title

    An efficient parallel algorithm for the assignment problem on the plane

  • Author

    Osiakwan, Constantine N K ; Akl, Selim G.

  • Author_Institution
    Bell Northern Research, Ottawa, Ont., Canada
  • fYear
    1992
  • fDate
    28-30 May 1992
  • Firstpage
    110
  • Lastpage
    113
  • Abstract
    The authors consider a parallel algorithm for minimum weight perfect matching on complete bipartite graphs induced by two disjoint sets of points on the plane. The algorithm is designed for the EREW PRAM or EREW RPRAM model of parallel computation with p (a function of n) processors. For points on the Euclidean plane, the algorithm executes in O(n3/p2+n 2 log n+n2.5 log n/p) time for p<√n. They achieve a perfect speedup algorithm when p⩾√n/log n and √n/p is not a constant
  • Keywords
    computational complexity; parallel algorithms; random-access storage; EREW PRAM; EREW RPRAM model; Euclidean plane; assignment problem; complete bipartite graphs; disjoint sets of points; minimum weight perfect matching; parallel algorithm; parallel computation; Algorithm design and analysis; Bipartite graph; Computational modeling; Concurrent computing; Councils; Design methodology; Information science; Parallel algorithms; Phase change random access memory;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computing and Information, 1992. Proceedings. ICCI '92., Fourth International Conference on
  • Conference_Location
    Toronto, Ont.
  • Print_ISBN
    0-8186-2812-X
  • Type

    conf

  • DOI
    10.1109/ICCI.1992.227693
  • Filename
    227693
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3256387