Computation of graph edit distance: Reasoning about optimality and speed-up

作者：

Highlights：

• Graph Edit Distance (GED) is the most used error-tolerant graph matching method.

• Bipartite graph matching algorithm (BP) is the most used algorithm to solve GED.

• 2 new versions of BP published that reduce the runtime but restrictions are imposed.

• We study how much extend these restrictions limits their applicability.

• Empirical validation shows new versions reduce runtime but keep recognition ratio.

摘要

•Graph Edit Distance (GED) is the most used error-tolerant graph matching method.•Bipartite graph matching algorithm (BP) is the most used algorithm to solve GED.•2 new versions of BP published that reduce the runtime but restrictions are imposed.•We study how much extend these restrictions limits their applicability.•Empirical validation shows new versions reduce runtime but keep recognition ratio.

论文关键词：Error-tolerant graph matching,Bipartite graph matching algorithm,Fast Bipartite,Square Fast Bipartite,Hungarian method,Jonker–Volgenant solver

论文评审过程：Received 2 December 2014, Revised 12 June 2015, Accepted 13 June 2015, Available online 25 June 2015, Version of Record 7 July 2015.

论文官网地址：https://doi.org/10.1016/j.imavis.2015.06.005