BOUNDS ON THE SIZE OF MERGING NETWORKS

Let M(m,n) be the minimum number of comparators needed in an (m,n)-merging network. Batcher's odd-even merge provides upper bounds, whereas the best general lower bounds were established by Yao and Yao (1976) and Miltersen et al. (to appear). In this paper, we concentrate on small fixed m and arbitrary n. M(1,n) = n has long been known. In their 1976 paper, Yao and Yao showed M(2,n) = [3n/2] and asked for the exact value of M(3,n). We prove M(3,n) = [(7n + 3)/4] for all n. Furthermore, M(4,n) > 11/6n, M(5,n) > 2n are shown, improving previous bounds. Some related questions are discussed.
Publisher
ELSEVIER SCIENCE BV
Issue Date
1995-08
Language
ENG
Citation

DISCRETE APPLIED MATHEMATICS, v.61, no.3, pp.187 - 194

ISSN
0166-218X
DOI
10.1016/0166-218X(94)00015-6
URI
http://hdl.handle.net/10203/73587
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 121
  • Download : 0
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 5 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0