AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

120 Minutes

Saarbrücken

The graph matching problem is to find a correspondence between vertices of two given graphs such that the number of induced edge disagreements is minimized. This problem is NP-hard in general. While the PATH algorithm achieves the state-of-the-art matching accuracy for random graphs, it is not known whether there is any guarantee for its matching accuracy in general. This thesis tries to answer the question above. It first studies the PATH algorithm in detail. Realizing that a direct proof is rather complicated, we analyze the algorithm’s performance based on experiments. It turns out that the solutions of the PATH algorithm can be arbitrarily  bad. On Cai-Fürer-Immerman graphs,  its  solutions give   worst

possible matching accuracy most of the time as graph size increases, which implies that such guarantee does not exist.

Andrea Ruffing

--email hidden

passcode not visible

logged in users only