5 papers
Distributed Symmetry Breaking on Hyperbolic Random Graphs
Yannic Maus, Janosch Ruff, Sonia Simons +1
Real-world networks like the internet share patterns like a power law degree distribution and a high clustering coefficient. Many of these properties are captured by the generative…
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…
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…
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.…
Strategic Network Creation for Enabling Greedy Routing
Julian Berger, Tobias Friedrich, Pascal Lenzner +2
Today we rely on networks that are created and maintained by smart devices. For such networks, there is no governing central authority but instead the network structure is shaped b…