2026-07-23T16:36:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20455 2024-07-18T12:12:42Z ddc:004 open_access

Multicoloured Hardcore Model: Fast Mixing and Its Applications as a Scheduling Algorithm Olesker-Taylor, Sam mixing time queueing theory hardcore model proper colourings independent set data transmission randomised algorithms routing scheduling multihop wireless networks In the hardcore model, certain vertices in a graph are active: the active vertices must form an independent set. We extend this to a multicoloured version: instead of simply being active or not, the active vertices are assigned a colour; active vertices of the same colour must not be adjacent. This models a scenario in which two neighbouring resources may interfere when active - eg, short-range radio communication. However, there are multiple channels (colours) available; they only interfere if both use the same channel. Other applications include routing in fibreoptic networks. We analyse Glauber dynamics. Vertices update their status at random times, at which a uniform colour is proposed: the vertex is assigned that colour if it is available; otherwise, it is set inactive. We find conditions for fast mixing of these dynamics. We also use them to model a queueing system: vertices only serve customers in their queue whilst active. The mixing estimates are applied to establish positive recurrence of the queue lengths, and bound their expectation in equilibrium. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sam Olesker-Taylor 2024 Is Part Of LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2024.20 urn:nbn:de:0030-drops-204558 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.20 eng https://creativecommons.org/licenses/by/4.0/legalcode