Max-Planck-Institut für Informatik
max planck institut
informatik
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
Language:English
Date, Time and Location
Date:Monday, 26 October 2015
Time:09:00
Duration:120 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
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.

Contact
Name(s):Andrea Ruffing
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Andrea Ruffing/MPI-INF, 10/23/2015 02:44 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Andrea Ruffing, 10/23/2015 02:46 PM -- Created document.