Addressing a hard graph colouring problem in Python

Speaker: Joan Vilaltella
Event: Python February Meetup
Date: 22 February 2018
Type: Talk
Language: English
Length: 20 minutes
Source: The announcement of the day on Meetup

About this talk

Graph edge colouring has many applications (scheduling, frequency assignment) but is widely believed to be computationally hard, even for graphs where each vertex has three neighbours (cubic graphs). In such difficult cases, heuristic algorithms are justified and may be empirically efficient in many specific instances. A simplified heuristic algorithm published by Fiol and Vilaltella in 2013 is reasonably fast on random graphs and also on many structured graphs. The Python language allows a clear and concise implementation of the algorithm.