You are here

Graph vertex colouring through clustering

e-Science Institute Public Lecture
István Juhos

Graph vertex colouring is part of an important family of computer science problems: constraint satisfaction. In previous decades, many combinatorial problem solvers have been introduced to tackle this problem. More recently, heuristic algorithms have become a popular approach. We introduce a new heuristic approach to approximate a solution to the graph vertex colouring problem. It uses a clustering applied to the vertices, where the clusters identify independent sets of vertices. These clusters are then translated into a valid colouring of the vertices.

The goal of the graph vertex colouring problem is to obtain the minimum number of clusters. To reach this goal, the clustering method relies on an informative similarity measurement between the vertices; this defines a topology of the graph. A rough approximation of the similarity is described by the constraints of the problem, i.e., the edges of the graph. This approximation is binary only as it reveals whether two vertices are similar or not. It represented through an adjacency matrix. A semidefinite program formulation of the Lovasz-theta function can modify this adjacency matrix to get a more informative similarity measurement. Based on this measurement, we show promising results of several clusterings.

Istvan Juhos is currently a PhD candidate at the University of Szeged, Hungary. He received his MSc and BSc degrees in mathematics and computer science from the University of Szeged. He has led several industrial research and development projects in the field of applied mathematics, quantum physics and artificial intelligence. His research interests include applied mathematics, graph theory and artificial intelligence. Within the latter he specialises in machine learning and data mining.

Date and time: 
Tuesday, 18 August, 2009 - 16:00
60 minutes