Approximate Graph Matching: approaches and a tool

			  Dennis Shasha


 Abstract: Approximate graph isomorphism and subgraph isomorphism are
 known to be NP-complete.  After studying many different heuristic
 approaches to this problem, we have worked out some new ones that work
 extremely well on random data and on real data from the National
 Cancer Institute.  The software is available and requires about 5
 minutes to download and start to use.
 
 This talk discusses the problem, some approaches including
 ours, and our experimental results.
 
 Dennis Shasha (shasha@cs.nyu.edu)
 
 Collaborators:
 Jason Wang, NJIT,
 Rosalba Guigno, University of Catania
 Jack Collins, National Cancer Institute