Superconcentrators of density 25.3

Kolmogorov V, Rolinek M. 2018. Superconcentrators of density 25.3. Ars Combinatoria. 141(10), 269–304.

Download (ext.)
Journal Article | Published | English

Scopus indexed
Department
Abstract
An N-superconcentrator is a directed, acyclic graph with N input nodes and N output nodes such that every subset of the inputs and every subset of the outputs of same cardinality can be connected by node-disjoint paths. It is known that linear-size and bounded-degree superconcentrators exist. We prove the existence of such superconcentrators with asymptotic density 25.3 (where the density is the number of edges divided by N). The previously best known densities were 28 [12] and 27.4136 [17].
Publishing Year
Date Published
2018-10-01
Journal Title
Ars Combinatoria
Publisher
Charles Babbage Research Centre
Volume
141
Issue
10
Page
269 - 304
ISSN
IST-REx-ID
18

Cite this

Kolmogorov V, Rolinek M. Superconcentrators of density 25.3. Ars Combinatoria. 2018;141(10):269-304.
Kolmogorov, V., & Rolinek, M. (2018). Superconcentrators of density 25.3. Ars Combinatoria. Charles Babbage Research Centre.
Kolmogorov, Vladimir, and Michal Rolinek. “Superconcentrators of Density 25.3.” Ars Combinatoria. Charles Babbage Research Centre, 2018.
V. Kolmogorov and M. Rolinek, “Superconcentrators of density 25.3,” Ars Combinatoria, vol. 141, no. 10. Charles Babbage Research Centre, pp. 269–304, 2018.
Kolmogorov V, Rolinek M. 2018. Superconcentrators of density 25.3. Ars Combinatoria. 141(10), 269–304.
Kolmogorov, Vladimir, and Michal Rolinek. “Superconcentrators of Density 25.3.” Ars Combinatoria, vol. 141, no. 10, Charles Babbage Research Centre, 2018, pp. 269–304.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Web of Science

View record in Web of Science®

Sources

arXiv 1405.7828

Search this title in

Google Scholar