Kolmogorov, Vladimir
Vladimir
Kolmogorov
Rolinek, Michal
Michal
Rolinek
Superconcentrators of density 25.3
Charles Babbage Research Centre
2018
2018-12-11T11:44:11Z
2019-08-02T12:37:26Z
journal_article
https://research-explorer.app.ist.ac.at/record/18
https://research-explorer.app.ist.ac.at/record/18.json
0381-7032
1405.7828
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].