Por favor, use este identificador para citar o enlazar a este item:
http://hdl.handle.net/10261/132969
COMPARTIR / EXPORTAR:
SHARE CORE BASE | |
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE | |
Título: | Filtering graphs to check isomorphism and extracting mapping by using the Conductance Electrical Model |
Autor: | Igelmo, Manuel; Sanfeliu, Alberto CSIC ORCID ; Sanfeliu, Alberto CSIC ORCID | Palabras clave: | Graph isomorphism Graph matching Conductances equivalent model Star method Graph filter |
Fecha de publicación: | 2016 | Editor: | Elsevier | Citación: | Pattern Recognition 58: 68-82 (2016) | Resumen: | This paper presents a new method of filtering graphs to check exact graph isomorphism and extracting their mapping. Each graph is modeled by a resistive electrical circuit using the Conductance Electrical Model (CEM). By using this model, a necessary condition to check the isomorphism of two graphs is that their equivalent resistances have the same values, but this is not enough, and we have to look for their mapping to find the sufficient condition. We can compute the isomorphism between two graphs in O(N3), where N is the order of the graph, if their star resistance values are different, otherwise the computational time is exponential, but only with respect to the number of repeated star resistance values, which usually is very small. We can use this technique to filter graphs that are not isomorphic and in case that they are, we can obtain their node mapping. A distinguishing feature over other methods is that, even if there exists repeated star resistance values, we can extract a partial node mapping (of all the nodes except the repeated ones and their neighbors) in O(N3). The paper presents the method and its application to detect isomorphic graphs in two well know graph databases, where some graphs have more than 600 nodes. | Versión del editor: | http://dx.doi.org/10.1016/j.patcog.2016.03.015 | URI: | http://hdl.handle.net/10261/132969 | DOI: | 10.1016/j.patcog.2016.03.015 | ISSN: | 0031-3203 |
Aparece en las colecciones: | (IRII) Artículos |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
Conductance-Electrical-Model.pdf | 402,94 kB | Adobe PDF | Visualizar/Abrir |
CORE Recommender
SCOPUSTM
Citations
1
checked on 08-abr-2024
WEB OF SCIENCETM
Citations
1
checked on 28-feb-2024
Page view(s)
233
checked on 22-abr-2024
Download(s)
223
checked on 22-abr-2024
Google ScholarTM
Check
Altmetric
Altmetric
NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.