Polynomial iterative algorithms for coloring and analyzing random graphs – Archive ouverte HAL
A. BraunsteinR. MuletA. Pagnani 1 M. WeigtR. Zecchina 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⟩ We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, […]