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