Greedy maximal independent sets via local limits

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Structural characterization of families of graphs (05C75) Randomized algorithms (68W20)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
The densest subgraph problem in sparse random graphs
Properties of regular graphs with large girth via local algorithms
Generalized random sequential adsorption on Erdős-Rényi random graphs
On a poset of trees
The average performance of the greedy matching algorithm
Asymptotic fringe distributions for general families of random trees
Random sequential adsorption on random trees
The Page-Rényi parking process
Parking on a random tree
The triangle-free process
Large independent sets in random regular graphs
Asymptotics in the random assignment problem
Branching processes, random trees, and a generalized scheme of arrangements of particles
Analysis of greedy algorithms on graphs with bounded degrees
The local limit of the uniform spanning tree on dense graphs
Local algorithms, regular graphs of large girth, and random regular graphs
Exact and approximate results for deposition and annihilation processes on graphs
On the average number of nodes in a subtree of a tree
Recurrence of distributional limits of finite planar graphs
Conceptual proofs of $L\log L$ criteria for mean behavior of branching processes
Differential equations for random processes and random graphs
Local algorithms for independent sets are half-optimal
The local limit of uniform spanning trees
A combinatorial approach for discrete car parking on random labelled trees
The jamming constant of uniform random graphs
Large independent sets in regular graphs of large girth
Limits of locally-globally convergent graph sequences
Processes on unimodular random networks
A note on the random greedy independent set algorithm
Walks and paths in trees
The Final Size of the $C_{\ell}$-free Process
Invariant Gaussian processes and independent sets on regular graphs of large girth
Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections
On graphs with randomly deleted edges
Randomized greedy matching
On colouring random graphs
Cliques in random graphs
Interactive proofs and the hardness of approximating cliques
The Greedy Independent Set in a Random Graph with Given Degrees
On the size of a random maximal graph
Reducibility among Combinatorial Problems
Large Deviation Principle for the Greedy Exploration Algorithm over Erd\"os-R\'enyi Graphs
Surprising identities for the greedy independent set on Cayley trees
The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)
When does the K₄‐free process stop?
Dynamic concentration of the triangle-free process
The C_ℓ‐free process
Limits of local algorithms over sparse random graphs
Large deviations of the greedy independent set algorithm on sparse random graphs
Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth

This page was built for publication: Greedy maximal independent sets via local limits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6541390)