The complexity of subgraph isomorphism for classes of partial k-trees
From MaRDI portal
Recommendations
- Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
- Faster algorithms for subgraph isomorphism of k-connected partial k-trees
Cites work
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Complexity of Finding Embeddings in a k-Tree
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Graph theory with applications
- scientific article; zbMATH DE number 4072379 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1301101 (Why is no real title available?)
- scientific article; zbMATH DE number 512967 (Why is no real title available?)
- scientific article; zbMATH DE number 1142299 (Why is no real title available?)
- On simple characterizations of k-trees
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Separating subgraphs in k-trees: Cables and caterpillars
- Subgraph isomorphism for biconnected outerplanar graphs in cubic time
- Subtree Isomorphism in O(n5/2)
- The Pathwidth and Treewidth of Cographs
- The subgraph isomorphism problem for outerplanar graphs
- Tree-width, path-width, and cutwidth
- Treewidth and pathwidth of permutation graphs
- Treewidth. Computations and approximations
- Triangulating graphs without asteroidal triples
Cited in
(28)- Approximating the maximum clique minor and some subgraph homeomorphism problems
- An exact algorithm for subgraph homeomorphism
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Faster algorithms for subgraph isomorphism of k-connected partial k-trees
- On maximum common subgraph problems in series-parallel graphs
- Polynomial time algorithms for variants of graph matching on partial k-trees
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
- On tradeoffs between width- and fill-like graph parameters
- Neighborhood-preserving mapping between trees
- Fixed-parameter tractability of treewidth and pathwidth
- On the Complexity of Extracting Subtree with Keeping Distinguishability
- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
- The subgraph isomorphism problem on a class of hyperedge replacement languages
- scientific article; zbMATH DE number 4043266 (Why is no real title available?)
- Transforming graph states using single-qubit operations
- Subgraph isomorphism in graph classes
- Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width
- Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
- scientific article; zbMATH DE number 1929947 (Why is no real title available?)
- The complexity of minimum-length path decompositions
- The Space Complexity of k-Tree Isomorphism
- Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
- Subgraph isomorphism on graph classes that exclude a substructure
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
- Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
- Efficient frequent connected subgraph mining in graphs of bounded tree-width
This page was built for publication: The complexity of subgraph isomorphism for classes of partial k-trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q671437)
