Smoothed Analysis on Connected Graphs

DOI10.1137/151002496zbMath1327.05312arXiv1307.4884OpenAlexW1637337126MaRDI QIDQ2947435

Wojciech Samotij, Daniel Reichman, Michael Krivelevich

Publication date: 23 September 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.4884

zbMATH Keywords

random walksgraph expansionsmall worlds

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Related Items

Some remarks on rainbow connectivity ⋮ The genus of the Erd\H{o}s-R\'enyi random graph and the fragile genus property ⋮ Cycle lengths in sparse random graphs ⋮ Speeding up random walk mixing by starting from a uniform vertex ⋮ Improved mixing rates of directed cycles by added connection ⋮ A framework for imperfectly observed networks ⋮ Isoperimetric numbers of randomly perturbed intersection graphs ⋮ Accelerated information dissemination on networks with local and global edges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sensitivity of mixing times
• Faster mixing and small bottlenecks
• The longest path in a random graph
• On the mixing time of a simple random walk on the super critical percolation cluster
• Renormalization group analysis of the small-world network model
• Heuristics for semirandom graph problems
• The phase transition in random graphs: A simple proof
• The mixing time of the giant component of a random graph
• On smoothed analysis in dense graphs and formulas
• Coloring complete bipartite graphs from random lists
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• How many random edges make a dense hypergraph non-2-colorable?
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• Smoothed analysis of algorithms
• The Diameter of a Cycle Plus a Random Matching
• Crossing numbers of random graphs
• How many random edges make a dense graph hamiltonian?
• Coloring Random and Semi-Random k-Colorable Graphs
• The Mixing Time of the Newman-Watts Small-World Model
• The diameter of randomly perturbed digraphs and some applications
• Probability and Computing
• On generalized graphs
• Expansion and Lack Thereof in Randomly Perturbed Graphs