Fast computation of Bipartite graph matching

• A sub-optimal algorithm is presented to compute the Graph Edit Distance.
• It obtains exactly the same distance value than the Bipartite algorithm.
• The computational cost is lower than the Bipartite one.
• Validation shows an important decrease on run time.

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.