3 papers
cs.DS2026
Distributed Colouring with 4/3 chi Colours for Hyperbolic Random Graphs
Kostas Lakis, Johannes Lengler, Adeline Pittet
We study distributed vertex colouring on Hyperbolic Random Graphs (HRGs), a geometric random graph model capturing key structural features of real-world networks. This provides a n…
cs.DS2025
Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
Nicolas El Maalouly, Kostas Lakis
The Exact Matching (EM) problem asks whether there exists a perfect matching which uses a prescribed number of red edges in a red/blue edge-colored graph. While there exists a rand…
math.PR2025
The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs
Zylan Benjert, Kostas Lakis, Johannes Lengler +1
We prove that the diameter of threshold (zero temperature) Geometric Inhomogeneous Random Graphs (GIRG) is . This has strong implications for the runtime of many distrib…