A Quadratic Programming Approach to the Graph Edit Distance Problem

Posted in Science on August 02, 2008


A Quadratic Programming Approach to the Graph Edit Distance Problem

In this paper we propose a quadratic programming approach to computing the edit distance of graphs. Whereas the standard edit distance is defined with respect to a minimum-cost edit path between graphs, we introduce the notion of fuzzy edit paths between graphs and provide a quadratic programming formulation for the minimization of fuzzy edit costs. Experiments on real-world graph data demonstrate that our proposed method is able to outperform the standard edit distance method in terms of recognition accuracy on two out of three data sets.

Author: Horst Bunke, University of Bern

Watch Video

Tags: Science, Lectures, Math, Computer Science, VideoLectures.Net, Graph Theory, Operations Research