𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A geometric construction of a superconcentrator of depth 2

✍ Scribed by Roy Meshulam

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
416 KB
Volume
32
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Superconcentrators of depth 2
Superconcentrators of depth 2
✍ Nicholas Pippenger πŸ“‚ Article πŸ“… 1982 πŸ› Elsevier Science 🌐 English βš– 468 KB
Superconcentrators of depths 2 and 3; od
Superconcentrators of depths 2 and 3; odd levels help (rarely)
✍ Noga Alon; Pavel Pudlak πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 401 KB

It is shown that the minimum possible number of edges in an n-superconcentrator of depth 3 is O(n log log n), whereas the minimum possible number of edges in an n-superconcentrator of depth 2 is Q(n(log n) 3/2) (and is O(n(log n)2)).