Colloquium Computer Science, Dr. Vincenzo Carletti, (University Salerno, Italy)

Title: ‘ Exact and Inexact Methods for Graph Similarity in Pattern Recognition ’

Abstract:

In Pattern Recognition two representations are commonly used to represent objects:

vectors and graphs. In the first case, the objects are represented as vectors of numerical features. Since this representation is widely used because of the strong mathematical theory concerning vectors, it is not able to properly represent structural information. On the other hand, graphs are more suited when it is needed to describe a set of objects together with their relationships. So that they are employed in many application fields where it is important to take into account the structure of the objects managed, such as biology, chemistry, social networks, databases and so on.

Unfortunately, measuring the distance between graphs is not easy as for vectors, because the Euclidean distance is not directly applicable. It is generally address by using graph matching algorithms and, in the worst case, is a NP-Complete problem. For this reason, during the last decades, a big effort has been spent to reduce the complexity, in the average case, by using different heuristics.

In this presentation I will describe two different approaches in the state of the art to compute the graph similarity in Structural Pattern Recognition

Colloquium coordinators are Prof.dr. M. Aiello (e-mail : M.Aiello rug.nl ) and
Prof.dr. M. Biehl (e-mail: M.Biehl rug.nl )

http://www.rug.nl/research/jbi/news/colloquia/computerscience