English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Approximate random k-colouring of a graph G=(V,E) is a very well studiedproblem in computer science and statistical physics. It amounts to constructinga k-colouring of G which is distributed close to Gibbs distribution, i.e. theuniform distribution over all the k-colourings of G. Here, we deal with theproblem when the underlying graph is an instance of Erdos-Renyi random graphG(n,p), where p=d/n and d is fixed.  We propose a novel efficient algorithm for approximate random k-colouringwith the following properties: given an instance of G(n,d/n) and for anyk>(2+\epsilon)d, it returns a k-colouring distributed within total variationdistance n^{-Omega(1)} from the Gibbs distribution, with probability1-n^{-Omega(1)}.  What we propose is neither a MCMC algorithm nor some algorithm inspired bythe message passing heuristics that were introduced by statistical physicist.Our algorithm is of combinatorial nature. It is based on a rather simplerecursion which reduces the random k-colouring of G(n,d/n) to randomk-colouring simpler subgraphs first.  The lower bound on the number of colours for our algorithm to run inpolynomial time is dramatically smaller than the corresponding bounds we havefor any previous algorithm.

A simple algorithm for random colouring G(n, d/n) using (2+\epsilon)d colours