Bounkong, S., van Mourik, Jort and Saad, David (2006). Coloring random graphs and maximizing local diversity. Physical Review E, 74 (5),
Abstract
We study a variation of the graph coloring problem on random graphs of finite average connectivity. Given the number of colors, we aim to maximize the number of different colors at neighboring vertices (i.e. one edge distance) of any vertex. Two efficient algorithms, belief propagation and Walksat are adapted to carry out this task. We present experimental results based on two types of random graphs for different system sizes and identify the critical value of the connectivity for the algorithms to find a perfect solution. The problem and the suggested algorithms have practical relevance since various applications, such as distributed storage, can be mapped onto this problem.
Publication DOI: | https://doi.org/10.1103/PhysRevE.74.057101 |
---|---|
Divisions: | College of Engineering & Physical Sciences > Systems analytics research institute (SARI) |
Additional Information: | Copyright of the American Physical Society |
Uncontrolled Keywords: | graph coloring,finite average connectivity,algorithms,graph colouring |
Publication ISSN: | 1550-2376 |
Last Modified: | 30 Sep 2024 09:45 |
Date Deposited: | 03 Aug 2009 11:51 |
Full Text Link: | |
Related URLs: |
http://www.scop ... tnerID=8YFLogxK
(Scopus URL) http://link.aip ... 005057101000001 (Publisher URL) |
PURE Output Type: | Article |
Published Date: | 2006-11-02 |
Authors: |
Bounkong, S.
van Mourik, Jort ( 0000-0002-3172-2714) Saad, David ( 0000-0001-9821-2623) |