On the complexity of finding iso- and other morphisms for partial k-trees
1992; Elsevier BV; Volume: 108; Issue: 1-3 Linguagem: Inglês
10.1016/0012-365x(92)90687-b
ISSN1872-681X
Autores Tópico(s)Computational Geometry and Mesh Generation
ResumoThe problems to decide whether H⩽G for input graphs H, G where ⩽ is ‘isomorphic to a subgraph’, ‘isomorphic to an induced subgraphs’, ‘isomorphic to a subdivision’, ‘isomorphic to a contraction’ or their combination, are NP-complete. We discuss the complexity of these problems when G is restricted to be a partial k-tree (in other terminology: to have tree-width ⩽k, to be k-decomposable, to have dimension ⩽k). Under this restriction the problems are still NP-complete in general, but there are polynomial algorithms under some natural restrictions imposed on H, for example when H has bounded degrees. We also give a polynomial time algorithm for the n disjoint connecting paths problem restricted to partial k-trees (with n part of input).
Referência(s)