## Abstract

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 log_{2} 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/log_{2} 3 = 1.8927…, we construct (n, n/2)-selectors of size at most Cn log_{2}n + O(n).

Original language | English |
---|---|

Title of host publication | Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings |

Editors | Takao Nishizeki, Toshihide Ibaraki, Kazuo Iwama, Masafurni Yamashita, Yasuyoshi Inagaki |

Publisher | Springer Verlag |

Pages | 165-174 |

Number of pages | 10 |

ISBN (Print) | 9783540562795 |

DOIs | |

Publication status | Published - 1992 |

Externally published | Yes |

Event | 3rd International Symposium on Algorithms and Computation, ISAAC 1992 - Nagoya, Japan Duration: Dec 16 1992 → Dec 18 1992 |

### Publication series

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

Volume | 650 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

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

Country/Territory | Japan |

City | Nagoya |

Period | 12/16/92 → 12/18/92 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint

Dive into the research topics of 'Selection networks with 8n log_{2}n size and O(log n) depth'. Together they form a unique fingerprint.