DC Field | Value | Language |
---|---|---|
dc.contributor.author | AIGNER, M | ko |
dc.contributor.author | Cheong, Otfried | ko |
dc.date.accessioned | 2013-03-02T12:47:20Z | - |
dc.date.available | 2013-03-02T12:47:20Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 1995-08 | - |
dc.identifier.citation | DISCRETE APPLIED MATHEMATICS, v.61, no.3, pp.187 - 194 | - |
dc.identifier.issn | 0166-218X | - |
dc.identifier.uri | http://hdl.handle.net/10203/73587 | - |
dc.description.abstract | 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. | - |
dc.language | English | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.title | BOUNDS ON THE SIZE OF MERGING NETWORKS | - |
dc.type | Article | - |
dc.identifier.wosid | A1995RQ62800001 | - |
dc.identifier.scopusid | 2-s2.0-0001518953 | - |
dc.type.rims | ART | - |
dc.citation.volume | 61 | - |
dc.citation.issue | 3 | - |
dc.citation.beginningpage | 187 | - |
dc.citation.endingpage | 194 | - |
dc.citation.publicationname | DISCRETE APPLIED MATHEMATICS | - |
dc.identifier.doi | 10.1016/0166-218X(94)00015-6 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.nonIdAuthor | AIGNER, M | - |
dc.type.journalArticle | Article | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.