Faster algorithms for subgraph isomorphism of k-connected partial k-trees

Authors
Dessmark, A Lingas, A Proskurowski, A
Citation
A. Dessmark et al., Faster algorithms for subgraph isomorphism of k-connected partial k-trees, ALGORITHMIC, 27(3-4), 2000, pp. 337-347
Citations number
17
Categorie Soggetti
Engineering Mathematics
Journal title
ALGORITHMICA
ISSN journal
01784617 → ACNP
Volume
27
Issue
3-4
Year of publication
2000
Pages
337 - 347
Database
ISI
SICI code
0178-4617(200007/08)27:3-4<337:FAFSIO>2.0.ZU;2-K
Abstract
The problem of determining whether a k-connected partial k-tree is isomorph ic 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 correspondin g bounds known in the literature. They rely in part on a new characterizati on of width-k tree-decomposition of k-connected partial k-trees.