Authors: Y. Tursunbay

Title of the article: On graph coloring in class of parallel local algorithms

Year: 2010, Issue: 6, Pages: 105-112

Branch of knowledge: Applied mathematics

Index UDK: 519.174.7, 004.75

DOI: -

Abstract: One of ways for improvement the performance of the distributed algorithm is representation of coloring strategy in algorithm which, as is known, is effective in non-distributed algorithms. In this paper we show that application of some sequential coloring algorithm heuristics such as the largest-first (SL), the smallest-last (SL) and the saturation largest-first (SLF) for some classes of graphs and for special cases of vertex coloring in the distributed algorithms give optimal or near optimal coloring.

Key words: graph coloring distributed algorithm local algorithm greedy algorithm perfect graph T-coloring sum coloring

CITE DOWNLOAD