The complexity of subgraph isomorphism for classes of partial k-trees
From MaRDI portal
Publication:671437
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
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
