Accés ràpid intranet

Més informació...

a a a
Inici

Report de recerca: DEIM-RR-13-003


Títol

Fast Computation of Bipartite Graph Matching

Autor/s

Francesc SERRATOSA CASANELLES

Data

20-11-2013

Grup de recerca

Sistemes Sensorials Aplicats a la Indstria

Tipus de report

Recerca

Idioma

Angls

Nombre de pàgines

12

Resum

We present a new algorithm to compute the Graph Edit Distance in a sub-optimal way. We demonstrate that the distance value is exactly the same than the one obtained by the algorithm called Bipartite but with a reduced run time. The only restriction we impose is that the edit costs have to be defined such that the Graph Edit Distance can be really defined as a distance function, that is, the cost of insertion plus deletion of nodes (or arcs) have to be lower or equal than the cost of substitution of nodes (or arcs). Empirical validation shows that higher is the order of the graphs, higher is the obtained Speed up.

Paraules Clau

Graph Edit Distance, Bipartite Graph Matching, Munkres? algorithm