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

IDA Technical Reports: abstract

Generated: Mon, 22 Dec 2014 23:03:15

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
<webmaster@ida.liu.se>