Articles producció científica> Enginyeria Informàtica i Matemàtiques

GRADUATED ASSIGNMENT ALGORITHM FOR MULTIPLE GRAPH MATCHING BASED ON A COMMON LABELING

  • Dades identificatives

    Identificador: imarina:9245871
    Autors:
    Sole-Ribalta, AlbertSerratosa, Francesc
    Resum:
    In pattern recognition applications, with the aim of increasing efficiency, it is useful to represent the elements by attributed graphs (which consider their structural properties). Under this structural representation of the elements some graph matching problems need a common labeling between the vertices of a set of graphs. Computing this common labeling is a NP-Complete problem. Nevertheless, some methodologies have been presented which obtain a sub-optimal solution in polynomial time. The drawback of these methods is that they rely on pairwise labeling computations, causing the methodologies not to consider the global information during the entire process. To solve this problem, we present a methodology which generates the common labeling by matching all graph nodes to a virtual node set. The method has been tested using three independent datasets, one synthetic and two real. Experimental results show that the presented method obtains better performance than the most popular common labeling algorithm with the same computational cost.
  • Altres:

    Autor segons l'article: Sole-Ribalta, Albert; Serratosa, Francesc
    Departament: Enginyeria Informàtica i Matemàtiques
    Autor/s de la URV: Serratosa Casanelles, Francesc d'Assís / Solé Ribalta, Albert
    Paraules clau: Retrieval Relaxation Pattern-recognition Multiple graph matching Median graphs Images Graph common labeling Graduated assignment Error tolerant graph isomorphism Distance Constellations Computation Classification Attributed graphs
    Resum: In pattern recognition applications, with the aim of increasing efficiency, it is useful to represent the elements by attributed graphs (which consider their structural properties). Under this structural representation of the elements some graph matching problems need a common labeling between the vertices of a set of graphs. Computing this common labeling is a NP-Complete problem. Nevertheless, some methodologies have been presented which obtain a sub-optimal solution in polynomial time. The drawback of these methods is that they rely on pairwise labeling computations, causing the methodologies not to consider the global information during the entire process. To solve this problem, we present a methodology which generates the common labeling by matching all graph nodes to a virtual node set. The method has been tested using three independent datasets, one synthetic and two real. Experimental results show that the presented method obtains better performance than the most popular common labeling algorithm with the same computational cost.
    Àrees temàtiques: Software Engenharias iv Educação Computer vision and pattern recognition Computer science, artificial intelligence Ciência da computação Astronomia / física Artificial intelligence
    Accès a la llicència d'ús: https://creativecommons.org/licenses/by/3.0/es/
    Adreça de correu electrònic de l'autor: albert.sole@urv.cat francesc.serratosa@urv.cat
    Identificador de l'autor: 0000-0002-2953-5338 0000-0001-6112-5913
    Data d'alta del registre: 2024-10-12
    Versió de l'article dipositat: info:eu-repo/semantics/acceptedVersion
    Enllaç font original: https://www.worldscientific.com/doi/abs/10.1142/S0218001413500018
    URL Document de llicència: https://repositori.urv.cat/ca/proteccio-de-dades/
    Referència a l'article segons font original: International Journal Of Pattern Recognition And Artificial Intelligence. 27 (1): 1350001-
    Referència de l'ítem segons les normes APA: Sole-Ribalta, Albert; Serratosa, Francesc (2013). GRADUATED ASSIGNMENT ALGORITHM FOR MULTIPLE GRAPH MATCHING BASED ON A COMMON LABELING. International Journal Of Pattern Recognition And Artificial Intelligence, 27(1), 1350001-. DOI: 10.1142/S0218001413500018
    DOI de l'article: 10.1142/S0218001413500018
    Entitat: Universitat Rovira i Virgili
    Any de publicació de la revista: 2013
    Tipus de publicació: Journal Publications
  • Paraules clau:

    Artificial Intelligence,Computer Science, Artificial Intelligence,Computer Vision and Pattern Recognition,Software
    Retrieval
    Relaxation
    Pattern-recognition
    Multiple graph matching
    Median graphs
    Images
    Graph common labeling
    Graduated assignment
    Error tolerant graph isomorphism
    Distance
    Constellations
    Computation
    Classification
    Attributed graphs
    Software
    Engenharias iv
    Educação
    Computer vision and pattern recognition
    Computer science, artificial intelligence
    Ciência da computação
    Astronomia / física
    Artificial intelligence
  • Documents:

  • Cerca a google

    Search to google scholar