On smoothed analysis in dense graphs and formulas

DOI10.1002/rsa.20097zbMath1108.05084MaRDI QIDQ3419587

Michael Krivelevich, Prasad Tetali, Benjamin Sudakov

Publication date: 7 February 2007

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20097

zbMATH Keywords

random graphs

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05D10: Ramsey theory

Related Items

The Effect of Adding Randomly Weighted Edges, Ramsey properties of randomly perturbed graphs: cliques and cycles, Maker-Breaker Games on Randomly Perturbed Graphs, Tree decompositions of graphs without large bipartite holes, Smoothed analysis of balancing networks, Tilings in Randomly Perturbed Dense Graphs, Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers, Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs, Expansion and Lack Thereof in Randomly Perturbed Graphs, Cycles and matchings in randomly perturbed digraphs and hypergraphs, Small rainbow cliques in randomly perturbed dense graphs, Isoperimetric numbers of randomly perturbed intersection graphs, Smoothed Analysis on Connected Graphs, Bounded-Degree Spanning Trees in Randomly Perturbed Graphs, Vertex Ramsey properties of randomly perturbed graphs, Smoothed Analysis of Local Search Algorithms

Cites Work

• Unnamed Item
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Smoothed analysis of algorithms