3 papers
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…
cs.DS2024
Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring
Samuel Baguley, Yannic Maus, Janosch Ruff +1
Hyperbolic random graphs inherit many properties that are present in real-world networks. The hyperbolic geometry imposes a scale-free network with a strong clustering coefficient.…