zbMATH — the first resource for mathematics

From expanders to better superconcentrators without cascading. (English) Zbl 0543.68049
Theoretical aspects of computer science, Symp., Paris 1984, Lect. Notes Comput. Sci. 166, 121-128 (1984).
Summary: [For the entire collection see Zbl 0533.00025.]
Superconcentration is a strong property of interconnection digraphs. We characterize its negation by existence of two disjoint and separated sets which shrink under the forward and backward neighbor relation, respectively. This enables a better, non-cascaded design of superconcentrators, explicit ones with edge density \(\leq 118\), random ones with edge density \(\leq 13\).

68R10 Graph theory (including graph drawing) in computer science
05C40 Connectivity
94C15 Applications of graph theory to circuits and networks
05C80 Random graphs (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments