A study of different matching heuristics

Abstract

A well-known combinatorial optimization problem is the graph partitioning problem. Since solving it optimally requires very much time, we have to settle for approximated methods. One such method is the multilevel k-way partitioning scheme. The overall idea is the following: The size of the graph is reduced during a process known as coarsening, where smaller and smaller graphs are made. Then a k-way partition is found from the much smaller graph and the graph and the partition is projected back to the original size.

In this master thesis, we study a central part of the multilevel k-way partitioning scheme, coarsening. In order make smaller and smaller graphs we use a technique known as matching. We introduce a new matching heuristic, global greedy heavy edge matching and perform a large number of experiments comparing it to other matching heuristics.

Our results include the discovery of two new partition vectors for the graph partitioning archive(http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/), and that using global greedy heavy edge matching generally produces better results than already existing matching heuristics.