Professor Fred DePiero
Research Home Page
Graphs are abstract descriptions of structures that may be used to describe chemical molecules, electrical circuits, or portions of an image or a speech signal. Finding matches or partial matches between two graphs is a very powerful technique in pattern recognition. Exact subgraph matching is a combinatorically-wicked problem. I work on algorithms that yield approximations, which can be computed in a deterministic amount of time. These are useful in real-time measurement applications.
I have developed two approximate methods of subgraph matching: one involving length-r paths ('LeRP') and the other using 'Basis Graphs'. My software is available for download and use for non-commercial, non-profit, non-military, non-defense purposes.
To appreciate the combinatoric nature of the graph matching problem, consider the following two graphs... Are these isomorphic, meaning do they have the same logical structure of interconnections between the labelled points?
The answer is: YES! The mapping is simply a to a, b to b... Spot checking the nodes will verify that this is true.
This type of matching process may be used to find common portions of chemical molecules, to verify that two large electrical circuits are the same, to recognize a spoken word or to identify a portion of an image.