Large deviations of the greedy independent set algorithm on sparse random graphs

DOI10.1002/rsa.21064zbMath1530.05180arXiv2011.04613OpenAlexW3099786723MaRDI QIDQ6052466

Brett Kolesnik

Publication date: 17 October 2023

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

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

zbMATH Keywords

greedy algorithmlarge deviationsindependent setEuler-Lagrange equationrandom graphdiscrete calculus

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Large deviations (60F10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Cites Work

• Scaling limits and generic bounds for exploration processes
• The critical random graph, with martingales
• Equivalence of discrete Euler equations and discrete Hamiltonian systems
• Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph
• On the probable behaviour of some algorithms for finding the stability number of a graph
• Solving Ordinary Differential Equations I
• The transitive closure of a random digraph
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• Symmetric sampling procedures, general epidemic processes and their threshold limit theorems
• On colouring random graphs
• Large Deviations with Diminishing Rates
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• A large‐deviations principle for all the cluster sizes of a sparse Erdős–Rényi graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Large deviations of the greedy independent set algorithm on sparse random graphs