Polynomial iterative algorithms for coloring and analyzing random graphs - Archive ouverte HAL Access content directly
Journal Articles Physical Review E Year : 2003

Polynomial iterative algorithms for coloring and analyzing random graphs

, , (1) , ,
1
A. Braunstein
  • Function : Author
R. Mulet
  • Function : Author
M. Weigt
  • Function : Author
R. Zecchina
  • Function : Author

Abstract

We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on q, we find with a one-step replica-symmetry breaking approximation the precise value of the critical average connectivity cq. Moreover, we show that below cq there exists a clustering phase c∈[cd,cq] in which ground states spontaneously divide into an exponential number of clusters. Furthermore, we extended our considerations to the case of single instances showing consistent results. This leads us to propose a different algorithm that is able to color in polynomial time random graphs in the hard but colorable region, i.e., when c∈[cd,cq].
Fichier principal
Vignette du fichier
1829463.pdf (171.03 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive

Dates and versions

insu-03726414 , version 1 (18-07-2022)

Identifiers

Cite

A. Braunstein, R. Mulet, A. Pagnani, M. Weigt, R. Zecchina. Polynomial iterative algorithms for coloring and analyzing random graphs. Physical Review E , 2003, 68, ⟨10.1103/PhysRevE.68.036702⟩. ⟨insu-03726414⟩
14 View
3 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More