Aarhus University Seal / Aarhus Universitets segl

The asymptotic complexity of merging networks

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

The asymptotic complexity of merging networks. / Miltersen, Peter Bro; Paterson, Mike; Tarui, Jun.

33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings.. IEEE Computer Society Press, 1992. p. 236-246.

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Miltersen, PB, Paterson, M & Tarui, J 1992, The asymptotic complexity of merging networks. in 33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings.. IEEE Computer Society Press, pp. 236-246, Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, United States, 24/10/1992. https://doi.org/10.1109/SFCS.1992.267768

APA

Miltersen, P. B., Paterson, M., & Tarui, J. (1992). The asymptotic complexity of merging networks. In 33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings. (pp. 236-246). IEEE Computer Society Press. https://doi.org/10.1109/SFCS.1992.267768

CBE

Miltersen PB, Paterson M, Tarui J. 1992. The asymptotic complexity of merging networks. In 33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings.. IEEE Computer Society Press. pp. 236-246. https://doi.org/10.1109/SFCS.1992.267768

MLA

Miltersen, Peter Bro, Mike Paterson and Jun Tarui "The asymptotic complexity of merging networks". 33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings.. IEEE Computer Society Press. 1992, 236-246. https://doi.org/10.1109/SFCS.1992.267768

Vancouver

Miltersen PB, Paterson M, Tarui J. The asymptotic complexity of merging networks. In 33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings.. IEEE Computer Society Press. 1992. p. 236-246 https://doi.org/10.1109/SFCS.1992.267768

Author

Miltersen, Peter Bro ; Paterson, Mike ; Tarui, Jun. / The asymptotic complexity of merging networks. 33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings.. IEEE Computer Society Press, 1992. pp. 236-246

Bibtex

@inproceedings{e9ad0cf0b1ba11df8c1a000ea68e967b,
title = "The asymptotic complexity of merging networks",
abstract = "Let M(m,n) be the minimum number of comparators needed in a comparator network that merges m elements x1⩽x2⩽. . .⩽xm and n elements y1 ⩽y2. . .⩽yn, where n⩾m. Batcher's odd-even merge yields the following upper bound: M(m,n)⩽1/2 (m+n)log2(m+1)+O( n); in particular, M(n,n)⩽n log2n+O(n). The authors prove the following lower bound that matches the upper bound above asymptotically as n⩾m→∞:M(m,n )⩾1/2(m+n)log2 (m+1)-O(m); in particular, M( n,n)⩾nlog2n-O (n). The authors' proof technique extends to give similarly tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging",
author = "Miltersen, {Peter Bro} and Mike Paterson and Jun Tarui",
year = "1992",
doi = "10.1109/SFCS.1992.267768",
language = "English",
isbn = "0-8186-2900-2",
pages = "236--246",
booktitle = "33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings.",
publisher = "IEEE Computer Society Press",
note = "null ; Conference date: 24-10-1992 Through 27-10-1992",

}

RIS

TY - GEN

T1 - The asymptotic complexity of merging networks

AU - Miltersen, Peter Bro

AU - Paterson, Mike

AU - Tarui, Jun

N1 - Conference code: 33

PY - 1992

Y1 - 1992

N2 - Let M(m,n) be the minimum number of comparators needed in a comparator network that merges m elements x1⩽x2⩽. . .⩽xm and n elements y1 ⩽y2. . .⩽yn, where n⩾m. Batcher's odd-even merge yields the following upper bound: M(m,n)⩽1/2 (m+n)log2(m+1)+O( n); in particular, M(n,n)⩽n log2n+O(n). The authors prove the following lower bound that matches the upper bound above asymptotically as n⩾m→∞:M(m,n )⩾1/2(m+n)log2 (m+1)-O(m); in particular, M( n,n)⩾nlog2n-O (n). The authors' proof technique extends to give similarly tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging

AB - Let M(m,n) be the minimum number of comparators needed in a comparator network that merges m elements x1⩽x2⩽. . .⩽xm and n elements y1 ⩽y2. . .⩽yn, where n⩾m. Batcher's odd-even merge yields the following upper bound: M(m,n)⩽1/2 (m+n)log2(m+1)+O( n); in particular, M(n,n)⩽n log2n+O(n). The authors prove the following lower bound that matches the upper bound above asymptotically as n⩾m→∞:M(m,n )⩾1/2(m+n)log2 (m+1)-O(m); in particular, M( n,n)⩾nlog2n-O (n). The authors' proof technique extends to give similarly tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging

U2 - 10.1109/SFCS.1992.267768

DO - 10.1109/SFCS.1992.267768

M3 - Article in proceedings

SN - 0-8186-2900-2

SP - 236

EP - 246

BT - 33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings.

PB - IEEE Computer Society Press

Y2 - 24 October 1992 through 27 October 1992

ER -