Minimizing Unsatisfaction in Colourful Neighbourhoods - Computer Science > Data Structures and AlgorithmsReportar como inadecuado




Minimizing Unsatisfaction in Colourful Neighbourhoods - Computer Science > Data Structures and Algorithms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Colouring sparse graphs under various restrictions is a theoretical problemof significant practical relevance. Here we consider the problem of maximizingthe number of different colours available at the nodes and theirneighbourhoods, given a predetermined number of colours. In the analyticalframework of a tree approximation, carried out at both zero and finitetemperatures, solutions obtained by population dynamics give rise to estimatesof the threshold connectivity for the incomplete to complete transition, whichare consistent with those of existing algorithms. The nature of the transitionas well as the validity of the tree approximation are investigated.



Autor: K. Y. Michael Wong, David Saad

Fuente: https://arxiv.org/







Documentos relacionados