The Taub Faculty of Computer Science Events and Talks

Graph matching is the problem of matching nodes of a graph in pairs such that the largest number of pairs is created or the largest sum of edge weights is obtained. Greedy graph matching provides us with a fast way to coarsen a given graph during graph partitioning. Direct algorithms on the CPU which perform such greedy matchings are simple and fast, but offer few handholds for parallelisation. To remedy this, we introduce a fine-grained shared-memory parallel algorithm for greedy matching, together with an implementation on the GPU, which is faster than the CPU algorithms and produces matchings of similar or better quality.

Another graph problem with much practical interest is that of graph clustering, where highly connected clusters with many internal edges and few external edges are determined. Agglomerative clustering is an effective greedy way to quickly generate graph clusterings of high quality. We introduce a fine-grained shared memory algorithm for agglomerative clustering on both the CPU and GPU. This heuristic algorithm is able to generate clusterings in very little time: an optimal clustering is obtained from a street network graph with 14 million vertices and 17 million edges in six seconds on the GPU. The clustering work was done as part of the 10th DIMACS challenge on graph partitioning and clustering.

Joint work with Bas Fagginger Auer.