On the complexity of submap isomorphism and maximum common submap problems

作者：

Highlights：

• We show that submap isomorphism is NP-complete.

• We give a Fixed Parameter Tractable algorithm for submap isomorphism.

• We experimentally evaluate it to search for patterns in segmented images.

• We show that maximum common connected submap is NP-hard.

摘要

Highlights•We show that submap isomorphism is NP-complete.•We give a Fixed Parameter Tractable algorithm for submap isomorphism.•We experimentally evaluate it to search for patterns in segmented images.•We show that maximum common connected submap is NP-hard.

论文关键词：Generalized map,Submap isomorphism,Maximum common submap,Complexity,Plane graph,Fixed-Parameter Tractable (FPT)

论文评审过程：Received 26 July 2013, Revised 19 May 2014, Accepted 28 May 2014, Available online 12 June 2014.

论文官网地址：https://doi.org/10.1016/j.patcog.2014.05.019