Publication

A conductance electrical model for representing and matching weighted undirected graphs

Conference Article

Conference

International Conference on Pattern Recognition (ICPR)

Edition

20th

Pages

958-961

Doc link

http://dx.doi.org/10.1109/ICPR.2010.240

File

Download the digital copy of the doc pdf document

Abstract

In this paper we propose a conductance electrical model to represent weighted undirected graphs that allows us to efficiently compute approximate graph isomorphism in large graphs. The model is built by transforming a graph into an electrical circuit. Edges in the graph become conductances in the electrical circuit. This model follows the laws of the electrical circuit theory and we can potentially use all the existing theory and tools of this field to derive other approximate techniques for graph matching. In the present work, we use the proposed circuital model to derive approximated graph isomorphism solutions.

Categories

pattern recognition.

Author keywords

graph isomorphism, conductance electrical model, weigthed undirected graphs

Scientific reference

M. Igelmo, A. Sanfeliu and M. Ferrer. A conductance electrical model for representing and matching weighted undirected graphs, 20th International Conference on Pattern Recognition, 2010, Istanbul, Turkey, pp. 958-961.