×

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\).

MSC:
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