Document Type

Technical Report

Publication Date

1985-06-01

Filename

WUCS-85-07.pdf

DOI:

10.7936/K7DV1H79

Technical Report Number

WUCS-85-07

Abstract

We define a natural probability distribution over the set of k-colorable graphs on n vertices and study the probable performance of several algorithms on graphs selected from this distribution. The main results are listed below. • We describe an algorithm to determine if a given n vertex graph is k-colorable, which runs in time O(n + m log k), where m is the number of edges. We show that this algorithm can successfully identify almost all random k-colorable graphs for constant or slowly growing values of k. • We show that an algorithm proposed by Brelas, and justified on experimental grounds can successfully k-color almost all random k-colorable graphs for constant or slowly growing values of k. We also describes an efficient implementation, which runs in time O(m log n). • We show that the performance of the well-known greedy algorithm for graph coloring is relatively poor for random k-colorable graphs. In addition to the analytical results, we present experimental data which provide more detailed information on the performance of these algorithms.

Comments

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

Download

Share

COinS