Efthymiou, Charilaos and Spirakis, Paul G ORCID: 0000-0001-5396-3749
(2008)
Random sampling of colourings of sparse random graphs with a constant
number of colours.
Theoretical Computer Science, 407 (1-3).
pp. 134-154.
Text
0804.2343v1.pdf - Unspecified Download (370kB) |
Abstract
In this work we present a simple and efficient algorithm which, with high probability, provides an almost uniform sample from the set of proper k-colourings on an instance of a sparse random graph G(n,d/n), where k=k(d) is a sufficiently large constant. Our algorithm is not based on the Markov Chain Monte Carlo method (M.C.M.C.). Instead, we provide a novel proof of correctness of our Algorithm that is based on interesting "spatial mixing" properties of colourings of G(n,d/n). Our result improves upon previous results (based on M.C.M.C.) that required a number of colours growing unboundedly with n.
Item Type: | Article |
---|---|
Additional Information: | 30 pages 0 figures, uses fullpage.sty |
Uncontrolled Keywords: | cs.DM, cs.DM, G.3; G.2.1; G.2.2 |
Depositing User: | Symplectic Admin |
Date Deposited: | 08 Apr 2016 11:11 |
Last Modified: | 18 Mar 2024 01:37 |
DOI: | 10.1016/j.tcs.2008.05.008 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3000318 |