Superconcentrators of depths 2 and 3; odd levels help (rarely)

Noga Alon; Pavel Pudlak

doi:10.1016/S0022-0000(05)80027-3

Superconcentrators of depths 2 and 3; odd levels help (rarely)

Noga Alon, Pavel Pudlak

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	194-202
Number of pages	9
Journal	Journal of Computer and System Sciences
Volume	48
Issue number	1
DOIs	https://doi.org/10.1016/S0022-0000(05)80027-3
State	Published - Feb 1994
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/S0022-0000(05)80027-3

Cite this

@article{5a5fe7d608874dca806035128811c0af,

title = "Superconcentrators of depths 2 and 3; odd levels help (rarely)",

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

author = "Noga Alon and Pavel Pudlak",

year = "1994",

month = feb,

doi = "10.1016/S0022-0000(05)80027-3",

language = "English (US)",

volume = "48",

pages = "194--202",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Superconcentrators of depths 2 and 3; odd levels help (rarely)

AU - Alon, Noga

AU - Pudlak, Pavel

PY - 1994/2

Y1 - 1994/2

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

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

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

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

U2 - 10.1016/S0022-0000(05)80027-3

DO - 10.1016/S0022-0000(05)80027-3

M3 - Article

AN - SCOPUS:0028371726

SN - 0022-0000

VL - 48

SP - 194

EP - 202

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 1

ER -

Superconcentrators of depths 2 and 3; odd levels help (rarely)

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this