Publication:4938890

Publication date: 28 August 2000

approximation; randomized algorithms; greedy algorithms; random graph process

05C80: Random graphs (graph-theoretic aspects)

05-02: Research exposition (monographs, survey articles) pertaining to combinatorics

05D40: Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)

Related Items

A Spatial Web Graph Model with Local Influence Regions, Hamiltonicity of random graphs produced by 2‐processes, Cleaning Random d-Regular Graphs with Brushes Using a Degree-Greedy Algorithm, Protean Graphs with a Variety of Ranking Schemes, Deterministic extractors for small-space sources, Concentration of first hitting times under additive drift, The independent neighborhoods process, A random triadic process, Properties of regular graphs with large girth via local algorithms, Dense subgraphs in the \(H\)-free process, Achlioptas process phase transitions are continuous, Book review of: D. P. Dubhashi and A. Panconesi, Concentration of measure for the analysis of randomized algorithms., The cook-book approach to the differential equation method, Connectivity threshold and recovery time in rank-based models for complex networks, Bootstrap percolation in living neural networks, Scale free properties of random \(k\)-trees, Cleaning random \(d\)-regular graphs with brooms, Phase transitions for modified Erdős--Rényi processes, An edge deletion model for complex networks, On the robustness of random \(k\)-cores, Birth control for giants, The early evolution of the \(H\)-free process, The triangle-free process, A central limit theorem via differential equations, Connected domination of regular graphs, Protean graphs with a variety of ranking schemes, Small maximal matchings in random graphs., Analysis of greedy algorithms on graphs with bounded degrees, Hamiltonian decompositions of random bipartite regular graphs., Maximum induced matchings of random cubic graphs, Bounds on the max and min bisection of random cubic and random 4-regular graphs, On the satisfiability threshold of formulas with three literals per clause, Random triangle removal, Bounds on the bisection width for random \(d\)-regular graphs, An algorithm for random signed 3-SAT with intervals, On the number of circuits in random graphs, A Power-of-Two-Choices Unbalanced Allocation Process, A Random Triadic Process