SECTION: Computer Technologies
SCIENTIFIC ORGANIZATION:
National Research University Higher School of Economics
REPORT FORM:
«Oral report»
AUTHOR(S)
OF THE REPORT:
Komosko L.F., Batsyn M.V.
SPEAKER:
Komosko L.F.
REPORT TITLE:
A fast greedy sequential heuristic for the vertex coloring problem
TALKING POINTS:

In the paper a fast greedy sequential heuristic for the vertex coloring problem is presented. Its high performance is based on two features. First, after coloring the current vertex we mark its color as forbidden for its neighbors. Second, we calculate a color for the current vertex and forbid it for its neighbors by means of bitwise operations with adjacency and color matrices. In the matrix of forbidden colors cij=0 if vertex j can be colored in color i and cij=1 if color i is forbidden for it. In comparison with the classical greedy heuristic the speedup reaches 28 times on DIMACS instances.