IDA Technical Reports: abstract

Lingas, A. and Syslo, M. M. (1989). A Polynomial-Time Algorithm for Subgraph Isomorphism of Two-Connected Series-Parallel Graphs. Technical Report LiTH-IDA-R-89-05, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of the 15th International Qolloquium on Automata, Languages and Programming, Tampere, Finland, July 1988. (bibtex),

Abstract: We present the first polynomial-time algorithm for the subgraph isomorphism problem restricted to two-connected series-parallel graphs, which uses a new decomposition technique. We also show that this problem is in random NC, and that it is in NC if the input graphs are of bounded valence.