Showing 2025Show all
2 papers · 1 filter
cs.DS2025
Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
Andreas Göbel, Janosch Ruff, Leon Schiller
We study efficient algorithms for recovering cliques in dense random intersection graphs (RIGs). In this model, cliques of size approximately are randomly plante…
cs.DS2025
On Distributed Colouring of Hyperbolic Random Graphs
Yannic Maus, Janosch Ruff
We analyse the performance of simple distributed colouring algorithms under the assumption that the input graph is a hyperbolic random graph (HRG), a generative model capturing key…