### 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 language | English (US) |
---|---|

Title of host publication | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

Publisher | ACM (Order n 508850) |

Pages | 98-102 |

Number of pages | 5 |

ISBN (Print) | 0897911512 |

State | Published - Jan 1 1985 |

Externally published | Yes |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Software

### Cite this

*Conference Proceedings of the Annual ACM Symposium on Theory of Computing*(pp. 98-102). ACM (Order n 508850).

}

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 -