Lingas, A. (1987). On Parallel Complexity of the Subgraph Isomorphism Problem. Technical Report LiTH-IDA-R-87-10, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: A simple parallel algorithm for subgraph isomorphism for graphs of valence d(n) and separator s(n) is presented. The algorithm runs in time O((logn)**3 d(n)s(n)) and uses exp(O(s(n)logn(d(n)+logn)) processors.
CS Dept TR Overview