Showing cs.DSShow all
2 papers · 1 filter
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…