Affordable Access

Publisher Website

Finding the median distributively

Authors
Journal
Journal of Computer and System Sciences
0022-0000
Publisher
Elsevier
Publication Date
Volume
24
Issue
2
Identifiers
DOI: 10.1016/0022-0000(82)90045-9
Disciplines
  • Communication
  • Computer Science

Abstract

Abstract We consider the problem of computing the median of a bag of 2n numbers by using communicating processes, each having some of the numbers in its local memory. The memories are assumed to be disjoint. For two processes an algorithm is given. Its time and space complexity is linear while the communication complexity is 2 log 2 n. A lower bound of log 2 n on the communication complexity is derived. Thus the algorithm is optimal up to a constant.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

A rare finding of the median nerve in the forearm.

on Clinical anatomy (New York, N.... November 2006

Finding the conditional location of a median path...

on Information and Computation Jan 01, 2008

[Surgery of the hand; new findings on distal lesio...

on Prensa médica argentina May 03, 1957
More articles like this..