On the complexity of Submap Isomorphism

Solnon C., Damiand G., De La Higuera C., Janodet J.-C.

Proc. of 9th Workshop on Graph-Based Representation in Pattern Recognition (GBR)
Lecture Notes in Computer Science 7877, pages 21-30, May 2013, Vienna, Austria

Abstract: Generalized maps describe the subdivision of objects in cells, and incidence and adjacency relations between cells, and they are widely used to model 2D and 3D images. Recently, we have defined submap isomorphism, which involves deciding if a copy of a pattern map may be found in a target map, and we have described a polynomial time algorithm for solving this problem when the pattern map is connected. In this paper, we show that submap isomorphism becomes NP-complete when the pattern map is not connected, by reducing the NP-complete problem Planar-4 3-SAT to it.

Keywords: Submap isomorphism; Complexity; NP-complete.

BibTex references

@InProceedings{SDHJ13,
      author = {Solnon C. and Damiand, G. and De La Higuera, C. and Janodet, J.-C.},
      title = {On the complexity of Submap Isomorphism},
      booktitle = {Proc. of 9th Workshop on Graph-Based Representation in Pattern Recognition (GBR)},
      series = {Lecture Notes in Computer Science},
      publisher = {Springer Berlin/Heidelberg},
      volume = {7877},
      pages = {21-30},
      month = {May},
      year = {2013},
      address = {Vienna, Austria},
      keywords = {Submap isomorphism; Complexity; NP-complete.},
      url = {https://doi.org/10.1007/978-3-642-38221-5_3}
}

Guillaume Damiand

On the complexity of Submap Isomorphism

Links:

BibTex references

Image