Large independent sets on random d-regular graphs with fixed degree d
Not on the map. Why?
Abstract (arXiv)
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. We studied experimentally the independence ratio obtained by the algorithm when d ∈ [3,100]. For all d ∈ [5,100], our results are larger than lower bounds calculated by exact methods, thus providing improved estimates of lower bounds.
Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 Mar 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2023: 3; 2024: 1.
4 papers.
- 2023Complex Recurrent Spectral Networkcited by 5
- 2023Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problemscited by 3
- 2023Engineered Ordinary Differential Equations as Classification Algorithm (EODECA): thorough characterization and testingcited by 0
- 2024A short review on the maximum clique problem algorithms with classical, AI, and quantum methodscited by 0
- 2024A short review on the maximum clique problem algorithms with classical, AI, and quantum methods13 Mar 2024
- 2023Engineered Ordinary Differential Equations as Classification Algorithm (EODECA): thorough characterization and testing22 Dec 2023
- 2023Complex Recurrent Spectral Network12 Dec 2023
- 2023Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems11 Sep 2023