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.
CS Dept TR Overview