The Greedy Independent Set in a Random Graph with Given Degrees

DOI10.1002/rsa.20716zbMath1386.05175arXiv1510.05560OpenAlexW2130651739MaRDI QIDQ4597601

Svante Janson, Malwina J. Luczak, Graham R. Brightwell

Publication date: 13 December 2017

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.05560

zbMATH Keywords

configuration modelgreedy independent setjamming constant

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

The jamming constant of uniform random graphs ⋮ Surprising identities for the greedy independent set on Cayley trees ⋮ Markovian online matching algorithms on large bipartite random graphs ⋮ Large deviations for the greedy exploration process on configuration models ⋮ Generalized random sequential adsorption on Erdős-Rényi random graphs ⋮ Corrected mean-field model for random sequential adsorption on random geometric graphs ⋮ The matching process and independent process in random regular graphs and hypergraphs

This page was built for publication: The Greedy Independent Set in a Random Graph with Given Degrees