An efficient algorithm for graph edit distance computation

作者：

Highlights：

• We identify invalid and redundant mappings and thus create a reduced search space.

• We use the beam-stack search to trade off memory utilization and backtracking calls.

• We extend our method to solve the GED-based graph similarity search problem.

摘要

•We identify invalid and redundant mappings and thus create a reduced search space.•We use the beam-stack search to trade off memory utilization and backtracking calls.•We extend our method to solve the GED-based graph similarity search problem.

论文关键词：Graph edit distance,Reduced search space,Beam-stack search,Heuristics,Graph similarity search

论文评审过程：Received 26 January 2018, Revised 26 September 2018, Accepted 2 October 2018, Available online 15 October 2018, Version of Record 21 November 2018.

论文官网地址：https://doi.org/10.1016/j.knosys.2018.10.002