EXPANDERS, SORTING IN ROUNDS AND SUPERCONCENTRATORS OF LIMITED DEPTH.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)

Abstract

We use finite geometries to construct explicitly highly expanding graphs with essentially the smallest possible number of edges. Our graphs enable us to improve significantly previous results on a parallel sorting problem, by describing an explicit algorithm to sort n elements in k time units using O(n**a**k) processors, where, e. g. , a//2 equals 7/4. Using our graphs we can also construct efficient n-superconcentrators of limited depth. For example, we construct an n superconcentrator of depth 3 with O(n**4**/**3) edges; better than the previous known results.

Original languageEnglish (US)
Title of host publicationConference Proceedings of the Annual ACM Symposium on Theory of Computing
PublisherACM (Order n 508850)
Pages98-102
Number of pages5
ISBN (Print)0897911512
StatePublished - Jan 1 1985
Externally publishedYes

Fingerprint

Sorting
Geometry

All Science Journal Classification (ASJC) codes

  • Software

Cite this

Alon, N. M. (1985). EXPANDERS, SORTING IN ROUNDS AND SUPERCONCENTRATORS OF LIMITED DEPTH. In Conference Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 98-102). ACM (Order n 508850).
Alon, Noga Mordechai. / EXPANDERS, SORTING IN ROUNDS AND SUPERCONCENTRATORS OF LIMITED DEPTH. Conference Proceedings of the Annual ACM Symposium on Theory of Computing. ACM (Order n 508850), 1985. pp. 98-102
@inproceedings{5837bfaf25c449f8be79fa63cb88923d,
title = "EXPANDERS, SORTING IN ROUNDS AND SUPERCONCENTRATORS OF LIMITED DEPTH.",
abstract = "We use finite geometries to construct explicitly highly expanding graphs with essentially the smallest possible number of edges. Our graphs enable us to improve significantly previous results on a parallel sorting problem, by describing an explicit algorithm to sort n elements in k time units using O(n**a**k) processors, where, e. g. , a//2 equals 7/4. Using our graphs we can also construct efficient n-superconcentrators of limited depth. For example, we construct an n superconcentrator of depth 3 with O(n**4**/**3) edges; better than the previous known results.",
author = "Alon, {Noga Mordechai}",
year = "1985",
month = "1",
day = "1",
language = "English (US)",
isbn = "0897911512",
pages = "98--102",
booktitle = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "ACM (Order n 508850)",

}

Alon, NM 1985, EXPANDERS, SORTING IN ROUNDS AND SUPERCONCENTRATORS OF LIMITED DEPTH. in Conference Proceedings of the Annual ACM Symposium on Theory of Computing. ACM (Order n 508850), pp. 98-102.

EXPANDERS, SORTING IN ROUNDS AND SUPERCONCENTRATORS OF LIMITED DEPTH. / Alon, Noga Mordechai.

Conference Proceedings of the Annual ACM Symposium on Theory of Computing. ACM (Order n 508850), 1985. p. 98-102.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - EXPANDERS, SORTING IN ROUNDS AND SUPERCONCENTRATORS OF LIMITED DEPTH.

AU - Alon, Noga Mordechai

PY - 1985/1/1

Y1 - 1985/1/1

N2 - We use finite geometries to construct explicitly highly expanding graphs with essentially the smallest possible number of edges. Our graphs enable us to improve significantly previous results on a parallel sorting problem, by describing an explicit algorithm to sort n elements in k time units using O(n**a**k) processors, where, e. g. , a//2 equals 7/4. Using our graphs we can also construct efficient n-superconcentrators of limited depth. For example, we construct an n superconcentrator of depth 3 with O(n**4**/**3) edges; better than the previous known results.

AB - We use finite geometries to construct explicitly highly expanding graphs with essentially the smallest possible number of edges. Our graphs enable us to improve significantly previous results on a parallel sorting problem, by describing an explicit algorithm to sort n elements in k time units using O(n**a**k) processors, where, e. g. , a//2 equals 7/4. Using our graphs we can also construct efficient n-superconcentrators of limited depth. For example, we construct an n superconcentrator of depth 3 with O(n**4**/**3) edges; better than the previous known results.

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

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

M3 - Conference contribution

SN - 0897911512

SP - 98

EP - 102

BT - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

PB - ACM (Order n 508850)

ER -

Alon NM. EXPANDERS, SORTING IN ROUNDS AND SUPERCONCENTRATORS OF LIMITED DEPTH. In Conference Proceedings of the Annual ACM Symposium on Theory of Computing. ACM (Order n 508850). 1985. p. 98-102