The complexity of subgraph isomorphism for classes of partial k-trees

DOI10.1016/0304-3975(96)00046-1zbMath0871.68139OpenAlexW2073919081MaRDI QIDQ671437

Naomi Nishimura, Arvind Kumar Gupta

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(96)00046-1

zbMATH Keywords

NP-completesubgraph isomorphism problembounded tree-width graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (15)

Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Transforming graph states using single-qubit operations ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ On maximum common subgraph problems in series-parallel graphs ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Subgraph isomorphism in graph classes ⋮ Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time ⋮ The complexity of minimum-length path decompositions ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ Embeddings of \(k\)-connected graphs of pathwidth \(k\) ⋮ Efficient frequent connected subgraph mining in graphs of bounded tree-width ⋮ The edge-disjoint paths problem is NP-complete for series-parallel graphs ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ An exact algorithm for subgraph homeomorphism

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Separating subgraphs in k-trees: Cables and caterpillars
• The subgraph isomorphism problem for outerplanar graphs
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Treewidth. Computations and approximations
• Tree-width, path-width, and cutwidth
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• On simple characterizations of k-trees
• Triangulating graphs without asteroidal triples
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Subtree Isomorphism in O(n5/2)
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Treewidth and pathwidth of permutation graphs
• The Pathwidth and Treewidth of Cographs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

This page was built for publication: The complexity of subgraph isomorphism for classes of partial k-trees