Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces |
| |
Authors: | Eli Shamir Eli Upfal |
| |
Affiliation: | Department of Computer Science, The Institute of Mathematics and Computer Science, The Hebrew University, Jerusalem, Israel |
| |
Abstract: | A sequential graph coloring algorithm and a strict distributed (broadcasting type) algorithm , and an analysis of their performance in scales of random graph spaces is presented. For a space of graphs with n vertices and a mean degree d(n), the number of colors produced is almost surely bounded by about d(n)/logd(n), which is almost surely not more than twice the chromatic number, and the distributed algorithm terminates in O(Max(d(n),logn)) steps. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|