Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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 plant…
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.DS2025
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.…