scientific article; zbMATH DE number 18979

MaRDI QIDQ3976404zbMATH OpenFDO

Authors Fan Chung

Publication date 26 June 1992

zbMATH Keywords

communication networksrandom-like graphstheoretical computer science

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Review text

[For the entire collection see Zbl 0733.00020.] For many problems in combinatorics, theoretical computer science and the theory of communication networks one may prove the existence of desired objects by probabilistic methods, but it is preferable to have explicit constructions. Often the desired objects are graphs with certain properties of random graphs. This paper reports on current progress on construction of such graphs.

Recommendations

• scientific article; zbMATH DE number 3924802
• scientific article; zbMATH DE number 18978
• scientific article; zbMATH DE number 1231233
• scientific article; zbMATH DE number 1540669
• Random Graphs
• scientific article; zbMATH DE number 5610906
• scientific article; zbMATH DE number 3875330
• scientific article; zbMATH DE number 863475
• scientific article; zbMATH DE number 3904630
• scientific article; zbMATH DE number 857026

Cited in

(10)

• Hermitian matrices and graphs: Singular values and discrepancy
• Explicit construction of graphs with an arbitrary large girth and of large size
• Logarithmic reduction of the level of randomness in some probabilistic geometric constructions
• The complexity of explicit constructions
• A new series of dense graphs of high girth
• Construction of expanders and superconcentrators using Kolmogorov complexity
• Optimal bounds for single-source Kolmogorov extractors
• Palindromic characteristic of committed graphs and some model theoretic properties
• Normalized Laplacian eigenvalues of hypergraphs
• The complexity of explicit constructions

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976404)