Smoothed Analysis on Connected Graphs
From MaRDI portal
Publication:2947435
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
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
