Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Explorations of the PATH Algorithm for Graph Matching
Speaker:Yanjie Wang
coming from:International Max Planck Research School for Computer Science - IMPRS
Speakers Bio:
Event Type:PhD Application Talk
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Monday, 26 October 2015
Duration:120 Minutes
Building:E1 4
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.

Name(s):Andrea Ruffing
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Andrea Ruffing, 10/23/2015 02:46 PM -- Created document.