Coloring random graphs and maximizing local diversity

Research output: Contribution to journalArticle

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.
Original languageEnglish
Article number057101
Number of pages4
JournalPhysical Review E
Volume74
Issue number5
DOIs
Publication statusPublished - 2 Nov 2006

Fingerprint

Random Graphs
Colouring
Connectivity
apexes
color
Belief Propagation
Graph Coloring
Critical value
Efficient Algorithms
Maximise
propagation
Experimental Results
Vertex of a graph
Color

Bibliographical note

Copyright of the American Physical Society

Keywords

  • graph coloring
  • finite average connectivity
  • algorithms
  • graph colouring

Cite this

@article{c46daf965f0443398c2d2e52263028a3,
title = "Coloring random graphs and maximizing local diversity",
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.",
keywords = "graph coloring, finite average connectivity, algorithms, graph colouring",
author = "S. Bounkong and {van Mourik}, Jort and David Saad",
note = "Copyright of the American Physical Society",
year = "2006",
month = "11",
day = "2",
doi = "10.1103/PhysRevE.74.057101",
language = "English",
volume = "74",
journal = "Physical Review E",
issn = "1539-3755",
publisher = "American Physical Society",
number = "5",

}

Coloring random graphs and maximizing local diversity. / Bounkong, S.; van Mourik, Jort; Saad, David.

In: Physical Review E, Vol. 74, No. 5, 057101, 02.11.2006.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Coloring random graphs and maximizing local diversity

AU - Bounkong, S.

AU - van Mourik, Jort

AU - Saad, David

N1 - Copyright of the American Physical Society

PY - 2006/11/2

Y1 - 2006/11/2

N2 - 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.

AB - 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.

KW - graph coloring

KW - finite average connectivity

KW - algorithms

KW - graph colouring

UR - http://www.scopus.com/inward/record.url?scp=33750710448&partnerID=8YFLogxK

UR - http://link.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=PLEEE8000074000005057101000001

U2 - 10.1103/PhysRevE.74.057101

DO - 10.1103/PhysRevE.74.057101

M3 - Article

VL - 74

JO - Physical Review E

JF - Physical Review E

SN - 1539-3755

IS - 5

M1 - 057101

ER -