Faster Algorithms for Subgraph Isomorphism of \sl k -Connected Partial \sl k -Trees

The problem of determining whether a k -connected partial k -tree is isomorphic to a subgraph of another partial k -tree is shown to be solvable in time O(n ^k+2 ) . The presented time-bounds considerably improve the corresponding bounds known in the literature. They rely in part on a new characterization of width-k tree-decomposition of k -connected partial k -trees.

Authors and Affiliations

1. Department of Computer Science, Lund University, Box 117, S-221 00 Lund, Sweden. Anders.Dessmark@cs.lth.se, Andrzej.Lingas@cs.lth.se., , , , , , SE

   A. Dessmark & A. Lingas

2. Department of Computer and Information Science, University of Oregon, Eugene, OR 97403, USA. andrzej@cs.uoregon.edu., , , , , , US

   A. Proskurowski

Received March 20, 1997; revised April 1, 1998.

Reprints and permissions