File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: An improved algorithm for finding the median distributively

TitleAn improved algorithm for finding the median distributively
Authors
Chin, FTing, HF
KeywordsDistributed Algorithms
Median Selection
Message Complexity
Issue Date1987
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica, 1987, v. 2 n. 1-4, p. 235-249 How to Cite?
DOI: http://dx.doi.org/10.1007/BF01840361
AbstractGiven two processes, each having a total-ordered set of n elements, we present a distributed algorithm for finding median of these 2 n elements using no more than log n +O(√log n) messages, but if the elements are distinct, only log n +O(1) messages will be required. The communication complexity of our algorithm is better than the previously known result which takes 2 log n messages. © 1987 Springer-Verlag New York Inc.
Persistent Identifierhttp://hdl.handle.net/10722/152402
ISSN
0178-4617
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.905
ISI Accession Number ID
WOS:A1987J151500007

 

DC FieldValueLanguage
dc.contributor.authorChin, Fen_US
dc.contributor.authorTing, HFen_US
dc.date.accessioned2012-06-26T06:38:06Z-
dc.date.available2012-06-26T06:38:06Z-
dc.date.issued1987en_US
dc.identifier.citationAlgorithmica, 1987, v. 2 n. 1-4, p. 235-249en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/10722/152402-
dc.description.abstractGiven two processes, each having a total-ordered set of n elements, we present a distributed algorithm for finding median of these 2 n elements using no more than log n +O(√log n) messages, but if the elements are distinct, only log n +O(1) messages will be required. The communication complexity of our algorithm is better than the previously known result which takes 2 log n messages. © 1987 Springer-Verlag New York Inc.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_US
dc.relation.ispartofAlgorithmicaen_US
dc.subjectDistributed Algorithmsen_US
dc.subjectMedian Selectionen_US
dc.subjectMessage Complexityen_US
dc.titleAn improved algorithm for finding the median distributivelyen_US
dc.typeArticleen_US
dc.identifier.emailChin, F:chin@cs.hku.hken_US
dc.identifier.emailTing, HF:hfting@cs.hku.hken_US
dc.identifier.authorityChin, F=rp00105en_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/BF01840361en_US
dc.identifier.scopuseid_2-s2.0-52449148031en_US
dc.identifier.volume2en_US
dc.identifier.issue1-4en_US
dc.identifier.spage235en_US
dc.identifier.epage249en_US
dc.identifier.isiWOS:A1987J151500007-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChin, F=7005101915en_US
dc.identifier.scopusauthoridTing, HF=7005654198en_US
dc.identifier.citeulike3313485-
dc.identifier.issnl0178-4617-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats