An Experimental Assessment of a Stochastic, Anytime, Decentralized, Soft Colourer for Sparse Graphs
Stephen Fitzpatrick5 
and Lambert Meertens5
| (5) |
Kestrel Institute, 3260 Hillview Avenue, Palo Alto, California, USA |
Abstract
This paper reports on a simple, decentralized, anytime, stochastic, soft graph-colouring algorithm. The algorithm is designed
to quickly reduce the number of colour conflicts in large, sparse graphs in a scalable, robust, low-cost manner. The algorithm
is experimentally evaluated in a framework motivated by its application to resource coordination in large, distributed networks.
Keywords Constraint optimization - conflict minimization - decentralized algorithms - anytime algorithms - graph colouring
This work is sponsored in part by DARPA through the ‘Autonomous Negotiating Teams’ program under contract #F30602-00-C-0014,
monitored by the Air Force Research Laboratory. The views and conclusions contained in this document are those of the authors
and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced
Research Projects Agency or the U.S. Government.
References secured to subscribers.