UC Santa Cruz

The community of researchers using nuclear magnetic resonance (NMR) spectroscopy to study the structure and dynamics of proteins are interested in solving the following problem. Let G and H be undirected graphs such that H is isomorphic to at least one subgraph of G. For each vertex v ∈ V (H), compute the set of vertices to which v is mapped by a subgraph isomorphism from H to a subgraph of G. This thesis introduces variations of this problem, reviews prior work, and proposes algorithmic and heuristic methods that outperform the incumbent state of the art on published benchmarks.