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

IDA Technical Reports: abstract

Generated: Wed, 21 Mar 2018 09:56:39

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.

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