Expansion and Lack Thereof in Randomly Perturbed Graphs
From MaRDI portal
Publication:5900217
DOI10.1007/978-3-540-78808-9_3zbMath1142.68310MaRDI QIDQ5900217
Publication date: 19 August 2008
Published in: Algorithms and Models for the Web-Graph (Search for Journal in Brave)
Full work available at URL: https://projecteuclid.org/euclid.im/1243430603
05C80: Random graphs (graph-theoretic aspects)
68M10: Network design and communication in computer systems
68R10: Graph theory (including graph drawing) in computer science
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Eigenvalues and expanders
- Approximate counting, uniform generation and rapidly mixing Markov chains
- The eigenvalues of random symmetric matrices
- Eigenvalues of random power law graphs
- On the scaling of the chemical distance in long-range percolation models
- The diameter of long-range percolation clusters on finite cycles
- The diameter of a long-range percolation graph
- The small-world phenomenon
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
- On smoothed analysis in dense graphs and formulas
- A proof of alon's second eigenvalue conjecture
- The Diameter of a Cycle Plus a Random Matching
- A Spectral Technique for Coloring Random 3-Colorable Graphs
- Adding random edges to dense graphs
- How many random edges make a dense graph hamiltonian?
- Smoothed analysis of algorithms
- Algorithms and Models for the Web-Graph
- Algorithms and Models for the Web-Graph
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Spectral techniques applied to sparse random graphs
- Collective dynamics of ‘small-world’ networks
- High Degree Vertices and Eigenvalues in the Preferential Attachment Graph
