On smoothed analysis in dense graphs and formulas

DOI10.1002/rsa.20097zbMath1108.05084OpenAlexW4247942259MaRDI 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

Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10)

Related Items (21)

Triangles in randomly perturbed graphs ⋮ Smoothed Analysis of Local Search Algorithms ⋮ Large Rainbow Cliques in Randomly Perturbed Dense Graphs ⋮ Cycles and matchings in randomly perturbed digraphs and hypergraphs ⋮ Smoothed Analysis on Connected Graphs ⋮ Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu ⋮ Factors in randomly perturbed hypergraphs ⋮ Bounded-Degree Spanning Trees in Randomly Perturbed Graphs ⋮ Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs ⋮ Tree decompositions of graphs without large bipartite holes ⋮ Smoothed analysis of balancing networks ⋮ Tilings in Randomly Perturbed Dense Graphs ⋮ Vertex Ramsey properties of randomly perturbed graphs ⋮ Expansion and Lack Thereof in Randomly Perturbed Graphs ⋮ Small rainbow cliques in randomly perturbed dense graphs ⋮ The Effect of Adding Randomly Weighted Edges ⋮ Ramsey properties of randomly perturbed graphs: cliques and cycles ⋮ Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers ⋮ An asymmetric random Rado theorem: 1-statement ⋮ Isoperimetric numbers of randomly perturbed intersection graphs ⋮ Maker-Breaker Games on Randomly Perturbed Graphs

Cites Work

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

This page was built for publication: On smoothed analysis in dense graphs and formulas