Smaller superconcentrators of density 28 |
| |
Authors: | Uwe Schöning |
| |
Affiliation: | Universität Ulm, Abteilung Theoretische Informatik, 89069 Ulm, Germany |
| |
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. Here it is proved that such superconcentrators exist (by a random construction of certain expander graphs as building blocks) having density 28 (where the density is the number of edges divided by N). The best known density before this paper was 34.2 U. Schöning, Construction of expanders and superconcentrators using Kolmogorov complexity, J. Random Structures Algorithms 17 (2000) 64-77] or 33 L.A. Bassalygo, Personal communication, 2004]. |
| |
Keywords: | Computational complexity Combinatorial problem Superconcentrator |
本文献已被 ScienceDirect 等数据库收录! |
|