IDA Technical Reports: abstract

Lingas, A. (1989). Subgraph Isomorphism for Connected Graphs of Bounded Valence and Bounded Separator is in NC. Technical Report LiTH-IDA-R-89-07, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of 1988 International Conference on Parallel Processing, Chicago, USA, August 1988. (bibtex),

Abstract: It is shown that the problem of subgraph isomorphism for connected graphs of bounded valence and bounded separator admits a deterministic parallel algorithm running in poly-log time and using a polynomial number of processors.