TY - GEN

T1 - Selection networks with 8n log2n size and O(log n) depth

AU - Jimbo, Shuji

AU - Maruoka, Akira

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 1992

Y1 - 1992

N2 - An (n, n/2)-selector is a comparator network that classifies a set of n values into two classes with the same number of values in such a way that each element in one class is at least as large as all of those in the other. Based on utilization of expanders, Pippenger[6] constructed (n, n/2)-selectors, whose size is asymptotic to 2n log2 n and whose depth is O((log n)2). In the same spirit, we obtain a relatively simple method to construct (n, n/2)-seleetors of depth O(log n). We construct (n, n/2)-selectors of size at most 8n log 2 n + O(n). Moreover, for arbitrary C > 3/log2 3 = 1.8927…, we construct (n, n/2)-selectors of size at most Cn log2n + O(n).

AB - An (n, n/2)-selector is a comparator network that classifies a set of n values into two classes with the same number of values in such a way that each element in one class is at least as large as all of those in the other. Based on utilization of expanders, Pippenger[6] constructed (n, n/2)-selectors, whose size is asymptotic to 2n log2 n and whose depth is O((log n)2). In the same spirit, we obtain a relatively simple method to construct (n, n/2)-seleetors of depth O(log n). We construct (n, n/2)-selectors of size at most 8n log 2 n + O(n). Moreover, for arbitrary C > 3/log2 3 = 1.8927…, we construct (n, n/2)-selectors of size at most Cn log2n + O(n).

UR - http://www.scopus.com/inward/record.url?scp=85029620405&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029620405&partnerID=8YFLogxK

U2 - 10.1007/3-540-56279-6_69

DO - 10.1007/3-540-56279-6_69

M3 - Conference contribution

AN - SCOPUS:85029620405

SN - 9783540562795

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 165

EP - 174

BT - Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings

A2 - Nishizeki, Takao

A2 - Ibaraki, Toshihide

A2 - Iwama, Kazuo

A2 - Yamashita, Masafurni

A2 - Inagaki, Yasuyoshi

PB - Springer Verlag

T2 - 3rd International Symposium on Algorithms and Computation, ISAAC 1992

Y2 - 16 December 1992 through 18 December 1992

ER -