We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Greedy maximal independent sets via local limits.
- Authors
Krivelevich, Michael; Mészáros, Tamás; Michaeli, Peleg; Shikhelman, Clara
- Abstract
The random greedy algorithm for finding a maximal independent set in a graph constructs a maximal independent set by inspecting the graph's vertices in a random order, adding the current vertex to the independent set if it is not adjacent to any previously added vertex. In this paper, we present a general framework for computing the asymptotic density of the random greedy independent set for sequences of (possibly random) graphs by employing a notion of local convergence. We use this framework to give straightforward proofs for results on previously studied families of graphs, like paths and binomial random graphs, and to study new ones, like random trees and sparse random planar graphs. We conclude by analysing the random greedy algorithm more closely when the base graph is a tree.
- Subjects
INDEPENDENT sets; RANDOM graphs; GREEDY algorithms; PLANAR graphs; TREE graphs
- Publication
Random Structures & Algorithms, 2024, Vol 64, Issue 4, p986
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.21200