The diameter of sparse random graphs

DOI10.1006/aama.2001.0720zbMath0977.05127OpenAlexW2032049676MaRDI QIDQ5939958

Publication date: 8 January 2002

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/aama.2001.0720

zbMATH Keywords

random graphs diameter evolution

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12)

Related Items

The mean and variance of the distribution of shortest path lengths of random regular graphs, TTLed Random Walks for Collaborative Monitoring in Mobile and Social Networks, Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks, Complex networks: structure and dynamics, Local weak convergence for PageRank, Distributed algorithms for random graphs, When is a scale-free graph ultra-small?, Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs, Generating large scale‐free networks with the Chung–Lu random graph model, Speeding up random walk mixing by starting from a uniform vertex, Localized phase for the Erdős-Rényi graph, Shortest hop multipath algorithm for wireless sensor networks, The continuum limit of critical random graphs, Concentration of rainbow \(k\)-connectivity of a multiplex random graph, The average distance and the diameter of dense random regular graphs, Decomposing Random Graphs into Few Cycles and Edges, Distributed Merkle's puzzles, Geodesic cycles in random graphs, Average update times for fully-dynamic all-pairs shortest paths, Diameters of random circulant graphs, Diameter in ultra‐small scale‐free random graphs, Probabilistic zero forcing on random graphs, Parsimonious flooding in dynamic graphs, Information Spreading in Dynamic Networks: An Analytical Approach, A modified bootstrap percolation on a random graph coupled with a lattice, Critical random graphs: Diameter and mixing time, Transience and recurrence of random walks on percolation clusters in an ultrametric space, Diameters in Supercritical Random Graphs Via First Passage Percolation, The Diameter of Sparse Random Graphs, Weighted distances in scale-free configuration models, On certain connectivity properties of the internet topology, Dynamics of opinion formation in hierarchical social networks: network structure and initial bias, Diameter, connectivity, and phase transition of the uniform random intersection graph, Limit theorems for network dependent random variables, Critical random graphs and the structure of a minimum spanning tree, Stochastic kronecker graphs, A distributed algorithm for finding Hamiltonian cycles in random graphs in \(O(\log n)\) time, A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs, Probabilistic analysis of efficiency and vulnerability in the Erdös–Rénji model, Statistical mechanics of complex networks, Index calculus in class groups of non-hyperelliptic curves of genus three, Anatomy of a young giant component in the random graph, A scale-free graph model based on bipartite graphs, Energy efficient randomised communication in unknown AdHoc networks, Topology discovery of sparse random graphs with few participants, A double large prime variation for small genus hyperelliptic index calculus, Accelerated information dissemination on networks with local and global edges, The chromatic discrepancy of graphs, Expansion in supercritical random subgraphs of the hypercube and its consequences, Connectedness strength of two vertices in an uncertain graph, On the Rigidity of Sparse Random Graphs

Cites Work