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

IDA Technical Reports: abstract

Generated: Fri, 21 Jul 2017 16:41:22

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