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

IDA Technical Reports: abstract

Generated: Fri, 31 Oct 2014 05:05:13

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.


Goto (at Linköping University): CS Dept TR Overview
<webmaster@ida.liu.se>