Subgraph isomorphism algorithms for multithreaded shared memory architectures

We study algorithms for the subgraph isomorphism problem implemented for massively multithreaded shared memory architectures such as the Cray XMT. Fast algorithms for the subgraph isomorphism problem will have important implications in biology. Recently the availability of genomic data has increased drastically due to the use of high-throughput methods which have made sequencing relatively easy. Automated techniques are needed in order to glean useful information from this wealth of data. Many of these techniques rely on solving an underlying subgraph isomorphism problem and will thus benefit from fast, highly parallel algorithms. By implementing these algorithms on a multithreaded shared memory platform, we minimize the communication latency due to the need for random access into the large graph which is inherent to these types of problems. We do not need to decompose the graph in a preprocessing step which can be time-consuming and of unknown benefit.