Research

Title

Fast Computation of Bipartite Graph Matching

Author/s

Francesc SERRATOSA CASANELLES

Date

20-11-2013

Research team

Sistemes Sensorials Aplicats a la Indústria

Research report type

Recerca

Language

Anglès

Number of pages

12

Summary

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.

Keywords

Graph Edit Distance, Bipartite Graph Matching, Munkres? algorithm