Fetching the paper…
Reading the bibliography…
This paper presents a linear prioritized local algorithm that computes large independent sets on a random $d$-regular graph with small and fixed degree $d$.
Reducibility among combinatorial problems
Richard M Karp · 1972
Earlier work this paper cites.
Finding a maximum independent set
Robert Endre Tarjan and Anthony E Trojanowski · 1977
Earlier work this paper cites.
The independence ratio of regular graphs
Béla Bollobás · 1981
Earlier work this paper cites.
A note on the independence number of triangle-free graphs
James B Shearer · 1983
Earlier work this paper cites.
lndependent sets in regular graphs of high girth
BD McKay · 1987
Earlier work this paper cites.
Differential equations for random processes and random graphs
Nicholas C Wormald et al · 1995
Earlier work this paper cites.
The maximum clique problem
Immanuel M Bomze, Marco Budinich, Panos M Pardalos, and Marcello Pelillo · 1999
Earlier work this paper cites.
Analysis of greedy algorithms on graphs with bounded degrees
Nicholas C Wormald · 2003
Earlier work this paper cites.
The p versus np problem
Stephen Cook · 2006
Cited alongside, same era.
Pattern recognition and machine learning
Christopher M Bishop · 2006
Cited alongside, same era.
Large independent sets in random regular graphs
William Duckworth and Michele Zito · 2009
Cited alongside, same era.
The hard-core model on random graphs revisited
Jean Barbier, Florent Krzakala, Lenka Zdeborová, and Pan Zhang · 2013
Cited alongside, same era.
Limits of local algorithms over sparse random graphs
David Gamarnik and Madhu Sudan · 2014
Cited alongside, same era.
Invariant gaussian processes and independent sets on regular graphs of large girth
Endre Csóka, Balázs Gerencsér, Viktor Harangi, and Bálint Virág · 2015
Cited alongside, same era.
Exact algorithms for maximum independent set
Mingyu Xiao and Hiroshi Nagamochi · 2017
Later among the works it cites.
Local algorithms for independent sets are half-optimal
Mustazee Rahman and Balint Virag · 2017
Later among the works it cites.
Cubic graphs with small independence ratio
József Balogh, Alexandr Kostochka, and Xujun Liu · 2017
Later among the works it cites.
Revisiting the challenges of maxclique
Raffaele Marino and Scott Kirkpatrick · 2018
Later among the works it cites.
Local algorithms, regular graphs of large girth, and random regular graphs
Carlos Hoppen and Nicholas Wormald · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Jian Ding, Allan Sly, Nike Sun, et al · 2016
Cited alongside, same era.
Independent sets and cuts in large-girth regular graphs
Endre Csóka · 2016
Cited alongside, same era.
https://github.com/raffaelemarino/large-independent-set-on-random-d-regular-graphs-with-small-and-fixed-connectivity-d
Cited in the paper.
Maria Chiara Angelini and Federico Ricci-Tersenghi · 2019
Later among the works it cites.
Optimal low-degree hardness of maximum independent set
Alexander S Wein · 2020
Closest in time.