2 citations · 2 across the 5 of their papers we have counts for
7 papers
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…
Geometric Routing in Geometric Inhomogeneous Random Graphs
Yu-Cheng Chiu, Marc Kaufmann, Kostas Lakis +1
We present the first rigorous analysis of decentralized geometric routing in Geometric Inhomogeneous Random Graphs (GIRGs), a weight-agnostic variant of the greedy routing protocol…
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…
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…
Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models
Marc Kaufmann, Kostas Lakis, Johannes Lengler +3
We study push-pull rumour spreading in ultra-small-world models for social networks where the degrees follow a power-law distribution. In a non-geometric setting, Fountoulakis, Pan…
Improved bounds for polylogarithmic graph distances in scale-free percolation and related models
Kostas Lakis, Johannes Lengler, Kalina Petrova +1
In this paper, we study graph distances in the geometric random graph models scale-free percolation SFP, geometric inhomogeneous random graphs GIRG, and hyperbolic random graphs HR…
Learning-Augmented Online TSP on Rings, Trees, Flowers and (almost) Everywhere Else
Evripidis Bampis, Bruno Escoffier, Themis Gouleakis +4
We study the Online Traveling Salesperson Problem (OLTSP) with predictions. In OLTSP, a sequence of initially unknown requests arrive over time at points (locations) of a metric sp…