scientific article

zbMath0673.05037MaRDI QIDQ3826581

Colin J. H. McDiarmid

Publication date: 1984

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

zbMATH Keywords

colouring algorithmsgreedy heuristicslarge random graphsprobabilistic analogy of algorithms

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

The jamming constant of uniform random graphs ⋮ Coloring random graphs ⋮ On the order of the largest induced tree in a random graph ⋮ Poisson convergence and Poisson processes with applications to random graphs ⋮ Expose-and-merge exploration and the chromatic number of a random graph ⋮ Large deviations of the greedy independent set algorithm on sparse random graphs ⋮ Near-optimal dominating sets in dense random graphs in polynomial expected time ⋮ Generalized random sequential adsorption on Erdős-Rényi random graphs ⋮ Greed is good: Approximating independent sets in sparse and bounded-degree graphs ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Scaling limits and generic bounds for exploration processes ⋮ Approximation algorithms in combinatorial scientific computing ⋮ The resolution complexity of random graph \(k\)-colorability

This page was built for publication: