Lower bounds for merging networks
type: Item
instance of: scholarly article
title: Lower bounds for merging networks
zbMATH Open document ID: 1007.68077
author: Shigeki Iwata
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
review text: A lower bound theorem is established for the number of comparators in a merging network. Let \(M(m,n)\) be the least number of comparators required in the \((m,n)\)-merging networks, and let \(C(m,n)\) be the number of comparators in Batcher's \((m,n)\)-merging network, respectively. We prove for \(n\geq 1\) that \(M(4,n)=C(4,n)\) for \(n\equiv 0,1,3\bmod 4, M(4,n)\geq C(4,n)-1\) for \(n\equiv 2\bmod 4\), and \(M(5,n)=C(5,n)\) for \(n\equiv 0,1,5\bmod 8\). Furthermore Batcher's \((6,8k+6)\)-, \((7,8k+7)\)-, and \((8,8k+8)\)-merging networks are optimal for \(k\geq 0\). Our lower bound for \((m,n)\)-merging networks, \(m\leq n\), has the same terms as \(C(m,n)\) has as far as \(n\) is concerned. Thus Batcher's \((m,n)\)-merging network is optimal up to a constant number of comparators, where the constant depends only on \(m\). An open problem posed by \textit{A. C.-C. Yao} and \textit{F. F. Yao} [J. Assoc. Comput. Mach. 23, 566-571 (1976; Zbl 0335.68034)] is solved: \(\lim_{n\to\infty}M(m,n)/n=\lceil\log m\rceil/2+m/2^{\lceil\log m\rceil}\).
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 1853189
MaRDI profile type: Publication
OpenAlex ID: W2025099704
cites work: Bounds on the size of merging networks
cites work: Q5585020
cites work: The asymptotic complexity of merging networks
cites work: Lower Bounds on Merging Networks
DOI: 10.1006/INCO.2001.2934
Recommended article: Bounds on the size of merging networks
Recommended article: The asymptotic complexity of merging networks
Recommended article: Q4230345
Recommended article: Some minimum merging networks
Recommended article: Mathematical Foundations of Computer Science 2003
Recommended article: Q4234092
Recommended article: Lower bounds on communication overlap of networks
Recommended article: On the asymptotic merging of the set of nodes in stochastic networks
Recommended article: Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults
Recommended article: Toward a Lower Bound for Sorting Networks
description: scientific article; zbMATH DE number 1853189