IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Sun, 04 Oct 2015 13:05:45

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.

Goto (at Linköping University): CS Dept TR Overview