English version


Guillaume Damiand

oPage d'accueil

oRecherches

oPublications

oEnseignements

oEncadrement de Thèses

oCV

oCoordonnées

oLiens

Efficient Search of Combinatorial Maps using Signatures

Gosselin S., Damiand G., Solnon C.
Theoretical Computer Science (TCS)
Volume 412, Number 15, pages 1392-1405, March 2011

Links:  PDF  Hal  Link  

Abstract: In this paper, we address the problem of computing canonical representations of n-dimensional combinatorial maps and of using them for efficiently searching for a map in a database. We define two combinatorial map signatures: the first one has a quadratic space complexity and may be used to decide of isomorphism with a new map in linear time whereas the second one has a linear space complexity and may be used to decide of isomorphism in quadratic time. We show that these signatures can be used to efficiently search for a map in a database.

Keywords: Combinatorial map; signature; map isomorphism.

BibTex references

@Article{GosselinAl11,
      author = {Gosselin, S. and Damiand, G. and Solnon, C.},
      title = {Efficient Search of Combinatorial Maps using Signatures},
      journal = {Theoretical Computer Science (TCS)},
      publisher = {Elsevier},
      volume = {412},
      number = {15},
      pages = {1392-1405},
      month = {March},
      year = {2011},
      keywords = {Combinatorial map; signature; map isomorphism.},
      url = {https://dx.doi.org/10.1016/j.tcs.2010.10.029}
}

Image


o [Retour]