scientific article; zbMATH DE number 1405894

Publication date: 28 August 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

approximation randomized algorithms greedy algorithms random graph process

Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

Total domination in regular graphs, Bounds on the max and min bisection of random cubic and random 4-regular graphs, Concentration of first hitting times under additive drift, On the number of circuits in random graphs, The independent neighborhoods process, Bounds on the bisection width for random \(d\)-regular graphs, An algorithm for random signed 3-SAT with intervals, Linear multi-objective drift analysis, The sharp threshold for making squares, A random triadic process, Properties of regular graphs with large girth via local algorithms, A Random Triadic Process, Asymptotic bounds on total domination in regular graphs, Greedy Matching in Bipartite Random Graphs, Bootstrap percolation in living neural networks, GHS algorithm on a graph with random weights, A gentle introduction to the differential equation method and dynamic concentration, On the modularity of 3‐regular random graphs and random graphs with given degree sequences, A randomized construction of high girth regular graphs, The number of \(n\)-queens configurations, Dense subgraphs in the \(H\)-free process, Bootstrap percolation in inhomogeneous random graphs, The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘), Small maximal matchings in random graphs., Markovian online matching algorithms on large bipartite random graphs, Scale free properties of random \(k\)-trees, Systemic cascades on inhomogeneous random financial networks, Orientability Thresholds for Random Hypergraphs, Convergence of Achlioptas Processes via Differential Equations with Unique Solutions, A Power-of-Two-Choices Unbalanced Allocation Process, Analysis of greedy algorithms on graphs with bounded degrees, Achlioptas process phase transitions are continuous, Hamiltonian decompositions of random bipartite regular graphs., 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, A Spatial Web Graph Model with Local Influence Regions, Cleaning random \(d\)-regular graphs with brooms, Deterministic extractors for small-space sources, Perfect matchings and Hamiltonian cycles in the preferential attachment model, Dynamics of random graphs with bounded degrees, Hamilton cycles in the semi-random graph process, Greedy Bipartite Matching in Random Type Poisson Arrival Model, \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph, Preferential attachment without vertex growth: emergence of the giant component, Critical random graphs and the differential equations technique, Birth control for giants, Phase transitions for modified Erdős--Rényi processes, Connectivity threshold and recovery time in rank-based models for complex networks, Hamiltonicity of random graphs produced by 2‐processes, On the satisfiability threshold of formulas with three literals per clause, The early evolution of the \(H\)-free process, An edge deletion model for complex networks, On conceptually simple algorithms for variants of online bipartite matching, Cleaning Random d-Regular Graphs with Brushes Using a Degree-Greedy Algorithm, A sharp threshold for bootstrap percolation in a random hypergraph, On the robustness of random \(k\)-cores, On the threshold problem for Latin boxes, Large girth approximate Steiner triple systems, A natural barrier in random greedy hypergraph matching, The triangle-free process, A central limit theorem via differential equations, Connected domination of regular graphs, Closing Gaps in Asymptotic Fair Division, Parallel execution of schedules with random dependency graph, Large triangle packings and Tuza’s conjecture in sparse random graphs, The condensation transition in random hypergraph 2-coloring, Independent dominating sets in graphs of girth five, Protean graphs with a variety of ranking schemes, Protean Graphs with a Variety of Ranking Schemes, Minimum 2-dominating sets in regular graphs, Perfect Matchings in the Semirandom Graph Process, Random triangle removal, The matching process and independent process in random regular graphs and hypergraphs, Maximum induced matchings of random cubic graphs