Document Type

Technical Report

Publication Date

1986-02-01

Filename

WUCS-86-2.pdf

Technical Report Number

WUCS-86-02

Abstract

We describe a simple and efficient heuristic algorithm for the graph coloring problem and show that for all k greater or equal to 1, it finds an optimal coloring for almost all k-colorable graphs. We also show that an algorithm proposed by Brelaz and justified on experimental grounds optimally colors almost all k-O(n+m logk) time when n is the number of vertices and m the number of edges. The new implementation of Brelaz's algorithm runs an O(mlogn) time. We observe that the popular greedy heuristic works poorly on k-colorable graphs.

Comments

Permanent URL: http://dx.doi.org/10.7936/K75T3HVM

Download

Share

COinS