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 (74)

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

This page was built for publication: