Complexity of Finding Embeddings in a k-Tree
From MaRDI portal
Publication:3751595
Recommendations
- scientific article; zbMATH DE number 3866594
- Sequential and parallel algorithms for embedding problems on classes of partial k-trees
- scientific article; zbMATH DE number 4094838
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
Cites work
- scientific article; zbMATH DE number 3884101 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A Characterization of Comparability Graphs and of Interval Graphs
- A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
- Characterization and Recognition of Partial 3-Trees
- Computing the Minimum Fill-In is NP-Complete
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Graph theory with applications
- Networks immune to isolated failures
- Networks immune to isolated line failures
- On simple characterizations of k-trees
- Reduced State EnumerationߞAnother Algorithm for Reliability Evaluation
- Separating subgraphs in k-trees: Cables and caterpillars
- Steiner trees, partial 2–trees, and minimum IFI networks
- Triangulated graphs and the elimination process
Cited in
(only showing first 100 items - show all)- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Efficient computation of the characteristic polynomial of a tree and related tasks
- Complexity of path-forming games
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Computing the branchwidth of interval graphs
- The complexity of minimum-length path decompositions
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- An implementation of the iterative proportional fitting procedure by propagation trees.
- Computing partial hypergraphs of bounded width
- Parameters tied to treewidth
- A logic-based analysis of Dempster-Shafer theory
- Mixed searching and proper-path-width
- The basic algorithm for pseudo-Boolean programming revisited
- Algorithms and complexity for Turaev-Viro invariants
- On the tree-width of planar graphs
- A \(c^k n\) 5-approximation algorithm for treewidth
- Heuristic and metaheuristic methods for computing graph treewidth
- Degree-constrained decompositions of graphs: Bounded treewidth and planarity
- A comparison of boundary graph grammars and context-free hypergraph grammars
- Maximum \(k\)-splittable \(s, t\)-flows
- A faster tree-decomposition based algorithm for counting linear extensions
- Decomposition width of matroids
- Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models
- The three-in-a-tree problem
- Bounded tree-width and LOGCFL
- A faster tree-decomposition based algorithm for counting linear extensions
- Recoloring graphs via tree decompositions
- Studies on hypergraphs. I: Hyperforests
- Characterization and complexity of uniformly nonprimitive labeled 2-structures
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Directed NLC-width
- All structured programs have small tree width and good register allocation
- Hybrid backtracking bounded by tree-decomposition of constraint networks
- The complexity of subgraph isomorphism for classes of partial k-trees
- Binary join trees for computing marginals in the Shenoy-Shafer architecture
- Tree-decompositions with bags of small diameter
- How to compute digraph width measures on directed co-graphs
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Graphs of bounded treewidth can be canonized in AC\(^1\)
- scientific article; zbMATH DE number 3866594 (Why is no real title available?)
- Tractability of most probable explanations in multidimensional Bayesian network classifiers
- The complexity of graph languages generated by hyperedge replacement
- An efficient tree decomposition method for permanents and mixed discriminants
- Upper bounds on the size of obstructions and intertwines
- Efficient pattern matching on graph patterns of bounded treewidth
- Minimal separators in extended \(P_4\)-laden graphs
- How to use the minimal separators of a graph for its chordal triangulation
- Counting \(H-\)colorings of partial \(k-\)trees
- Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
- Regularity and locality in \(k\)-terminal graphs
- Constant-degree graph expansions that preserve treewidth
- Edge and node searching problems on trees
- \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
- An Experimental Study of the Treewidth of Real-World Graph Data
- Achievable sets, brambles, and sparse treewidth obstructions
- Tree-width, path-width, and cutwidth
- Tree-decompositions of small pathwidth
- Faster computation of the Robinson-Foulds distance between phylogenetic networks
- Node-searching problem on block graphs
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Treewidth lower bounds with brambles
- PRM inference using Jaffray \& Faÿ's local conditioning
- Inference in belief networks: A procedural guide
- Approximation algorithms for digraph width parameters
- Topological parameters for time-space tradeoff
- Independent sets in asteroidal triple-free graphs
- Treewidth and pathwidth of permutation graphs
- Canonical representations of partial 2- and 3-trees
- Computing bond orders in molecule graphs
- Searching for a Visible, Lazy Fugitive
- scientific article; zbMATH DE number 4094838 (Why is no real title available?)
- The connected critical node problem
- Efficient problem solving on tree decompositions using binary decision diagrams
- Decomposing SAT Instances with Pseudo Backbones
- Graph decompositions and tree automata in reasoning with uncertainty
- On the maximum weight minimal separator
- A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
- scientific article; zbMATH DE number 7626718 (Why is no real title available?)
- Parameterised complexity of model checking and satisfiability in propositional dependence logic
- On hyperedge replacement and BNLC graph grammars
- Adapting the directed grid theorem into an FPT algorithm
- On efficiently solvable cases of quantum \(k\)-SAT
- Understanding the scalability of Bayesian network inference using clique tree growth curves
- Graph isomorphism restricted by lists
- Approximation hardness of domination problems on generalized convex graphs
- Shape measures of random increasing \(k\)-trees
- Characterizing marginalization and incremental operations on the Bayes tree
- Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- Variable neighborhood search for graphical model energy minimization
- Decomposability helps for deciding logics of knowledge and belief
- On the complexity of planning for agent teams and its implications for single agent planning
- Interval degree and bandwidth of a graph
- Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?
- Weighted Treewidth Algorithmic Techniques and Results
- Stability, vertex stability, and unfrozenness for special graph classes
- Tangle bases: Revisited
- Sequential and parallel algorithms for embedding problems on classes of partial k-trees
- Domino treewidth
- Finding good tree decompositions by local search
This page was built for publication: Complexity of Finding Embeddings in a k-Tree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3751595)
