David Eppstein <eppstein @ ics . uci . edu> (email mangled to prevent spamming)
Dept. of Information and Computer Science University of California Irvine, CA 92717-3425 USA
Abstract:
This file is a bibliography of papers on subgraph isomorphism algorithms and their applications. Subgraph isomorphism is an important and very general form of exact pattern matching. Theoretically, subgraph isomorphism is a common generalization of many important graph problems including finding Hamiltonian paths, cliques, matchings, girth, and shortest paths. Variations of subgraph isomorphism have also been used to model such varied practical problems as molecular structure comparison, integrated circuit testing, microprogrammed controller optimization, analysis of Chinese ideographs, robot motion planning, semantic network retrieval, and polyhedral object recognition.
Keywords:
subgraph isomorphism, graph matching, largest common subgraph, subgraph homeomorphism, graph minors
