• DocumentCode
    3486566
  • Title

    Sorting-based selection algorithms for hypercubic networks

  • Author

    Berthome, P. ; Ferreira, Andre ; Maggs, B.M. ; Perennes, S. ; Plaxton, C.G.

  • Author_Institution
    Lab. de Inf. du Parallelisme, Ecole Normale Superieure de Lyon, France
  • fYear
    1993
  • fDate
    13-16 Apr 1993
  • Firstpage
    89
  • Lastpage
    95
  • Abstract
    This paper presents several deterministic algorithms for selecting the kth largest record from a set of n records on any n-node hypercubic network. All of the algorithms are based on the selection algorithm of Cole and Yap (1985), as well as on various sorting algorithms for hypercubic networks. The authors fastest algorithm runs in O(lg n lg*n) time, very nearly matching the trivial Ω(lg n) lower bound. Previously, the best upper bound known for selection was O(lg n lg lg n)
  • Keywords
    hypercube networks; sorting; deterministic algorithms; hypercubic networks; kth largest record; sorting based selection algorithms; upper bound; Algorithms; Hypercubes; Joining processes; Parallel processing; Partial response channels; Radio access networks; Sampling methods; Sorting; Statistics; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Processing Symposium, 1993., Proceedings of Seventh International
  • Conference_Location
    Newport, CA
  • Print_ISBN
    0-8186-3442-1
  • Type

    conf

  • DOI
    10.1109/IPPS.1993.262861
  • Filename
    262861
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3486566