Cover Image

A note on the random greedy independent set algorithm

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bennett, Patrick, Bohman, Tom
Format:	Preprint
Published:	2013
Subjects:	Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The largest $K_r$-free set of vertices in a random graph
by: Bohman, Tom, et al.
Published: (2026)

A note on Two-Point Concentration of the Independence Number of $G_{n,m}$
by: Bohman, Tom, et al.
Published: (2024)

Large deviations of the greedy independent set algorithm on sparse random graphs
by: Kolesnik, Brett
Published: (2020)

Surprising identities for the greedy independent set on Cayley trees
by: Contat, Alice
Published: (2021)

Completely greedy coin sets
by: Young, Andrew J.
Published: (2024)

Two-Point Concentration of the Independence Number of the Random Graph
by: Bohman, Tom, et al.
Published: (2022)

A note on the alternating number of independent sets in a graph
by: Cutler, Jonathan, et al.
Published: (2024)

A Critical Probability for Biclique Partition of $G_{n,p}$
by: Bohman, Tom, et al.
Published: (2022)

A note on multicolour Ramsey numbers and random sphere graphs
by: Attwa, Yamaan, et al.
Published: (2026)

The intersection of a random geometric graph with an Erdős-Rényi graph
by: Bennett, Patrick, et al.
Published: (2024)

Generalising the maximum independent set algorithm via Boolean networks
by: Gadouleau, Maximilien, et al.
Published: (2024)

Asymptotically optimal constant weight codes with even distance
by: Bennett, Patrick
Published: (2024)

A note on hyperseparating set systems
by: Gerbner, Dániel
Published: (2026)

Two-Point Concentration of the Domination Number of Random Graphs
by: Bohman, Tom, et al.
Published: (2024)

Counting independent sets in structured graphs
by: Bucić, Matija, et al.
Published: (2024)

A note on strong blocking sets and higgledy-piggledy sets of lines
by: Lia, Stefano, et al.
Published: (2024)

Monochromatic products in random integer sets
by: Lidón, Roger, et al.
Published: (2025)

The minimum number of maximal independent sets in graphs with given order and independence number
by: Tian, Yuting, et al.
Published: (2024)

Star decompositions and independent sets in random regular graphs
by: Harangi, Viktor
Published: (2025)

Partition subcubic planar graphs into independent sets
by: Liu, Xujun, et al.
Published: (2024)

Dowling's polynomial conjecture for independent sets of matroids
by: Cao, Shiqi, et al.
Published: (2026)

A note on the width of sparse random graphs
by: Do, Tuan Anh, et al.
Published: (2022)

Extremal independence in discrete random systems
by: Isaev, Mikhail, et al.
Published: (2021)

Sumsets of random sets
by: Nenadov, Rajko, et al.
Published: (2026)

Counting independent sets in expanding bipartite regular graphs
by: Collares, Maurício, et al.
Published: (2025)

Hindrance from a wasteful common independent set
by: Joó, Attila
Published: (2025)

An exponentially small gap of the Perron vector on independent sets
by: Chen, Hongzhang, et al.
Published: (2026)

A note on finding large transversals efficiently
by: Anastos, Michael, et al.
Published: (2024)

Balanced independent sets and colorings of hypergraphs
by: Dhawan, Abhishek
Published: (2023)

A note on inverting the dijoin of oriented graphs
by: Behague, Natalie, et al.
Published: (2024)

The third positive element in the greedy $B_h$-set
by: Nathanson, Melvyn B.
Published: (2023)

The fourth positive element in the greedy $B_h$-set
by: Nathanson, Melvyn B., et al.
Published: (2023)

Some online Maker-Breaker games
by: Bennett, Patrick, et al.
Published: (2024)

Edge-coloring $K_{n, n}$ with no 2-colored $C_{2k}$
by: Bal, Deepak, et al.
Published: (2025)

Counting independent sets in regular graphs with bounded independence number
by: Galvin, David, et al.
Published: (2024)

A remark on the independence number of sparse random Cayley sum graphs
by: Nenadov, Rajko
Published: (2025)

Counting independent sets in percolated graphs via the Ising model
by: Geisler, Anna, et al.
Published: (2025)

A note on transverse sets and bilinear varieties
by: Milićević, Luka
Published: (2023)

A fixed-point theorem for face maps, or deletion-tolerant random finite sets
by: Hutchcroft, Tom, et al.
Published: (2025)

A note on the second-largest number of dissociation sets in connected graphs
by: Li, Pingshan, et al.
Published: (2025)