Lingas, A. (1985). Subgraph Isomorphism for Easily Separable Graphs of Bounded Valence. Technical Report LiTH-IDA-R-85-15, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of International Workshop on Graphtheoretic Concepts in Computer Science, Castle Schwanberg, Wuerzburg, Germany, June 18-21, 1985. (bibtex),
Abstract: A general method for solving the subgraph isomorphism for connected graphs with s(n)-separator and valence bounded by d(n) is presented. The method takes exp(O((d(n)+logn)s(n)logn)) time.
CS Dept TR Overview