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)- Two strikes against perfect phylogeny
- Chordal networks of polynomial ideals
- An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
- Positive-instance driven dynamic programming for treewidth
- Graphical Models and Message-Passing Algorithms: Some Introductory Lectures
- Lex M versus MCS-M
- Trees, grids, and MSO decidability: from graphs to matroids
- Directed NLC-width
- Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
- Learning tractable Bayesian networks in the space of elimination orders
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- The parametrized complexity of knot polynomials
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
- Computational aspects of treewidth for graph
- Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
- Domino treewidth
- A logic-based analysis of Dempster-Shafer theory
- How to use the minimal separators of a graph for its chordal triangulation
- Turbocharging treewidth heuristics
- Upper bounds on the size of obstructions and intertwines
- Improving robustness of next-hop routing
- The complexity of pursuit on a graph
- Probability propagation
- Treewidth and minimum fill-in on permutation graphs in linear time
- Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited
- Precoloring extension. I: Interval graphs
- A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
- A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
- Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- Approximating Pathwidth for Graphs of Small Treewidth
- Symbolic techniques in satisfiability solving
- Theory of evidence ? A survey of its mathematical foundations, applications and computational aspects
- Hardness of computing width parameters based on branch decompositions over the vertex set
- On the hardness of palletizing bins using FIFO queues
- An exact method for graph coloring
- Treewidth, crushing and hyperbolic volume
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Decomposability helps for deciding logics of knowledge and belief
- A Logical Approach to Constraint Satisfaction
- Heuristic and metaheuristic methods for computing graph treewidth
- The dag-width of directed graphs
- Tree decomposition and discrete optimization problems: a survey
- Treewidth governs the complexity of target set selection
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Tractability in constraint satisfaction problems: a survey
- The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
- A comparison of graphical techniques for decision analysis
- Algorithmic uses of the Feferman-Vaught theorem
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- Approximating the treewidth of AT-free graphs.
- Courcelle's theorem -- a game-theoretic approach
- \(k\)-NLC graphs and polynomial algorithms
- Complexity of path-forming games
- Inference in belief networks: A procedural guide
- On tradeoffs between width- and fill-like graph parameters
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- Decomposition width of matroids
- Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models
- Constructive linear time algorithms for branchwidth
- scientific article; zbMATH DE number 4094838 (Why is no real title available?)
- Stability, vertex stability, and unfrozenness for special graph classes
- Safe separators for treewidth
- Conjunctive query containment revisited
- The power of non-ground rules in Answer Set Programming
- Tree-decompositions of small pathwidth
- Constant-degree graph expansions that preserve treewidth
- A sufficiently fast algorithm for finding close to optimal clique trees
- Learning bounded tree-width Bayesian networks via sampling
- Characterizations and algorithmic applications of chordal graph embeddings
- An annotated bibliography on guaranteed graph searching
- Encoding Treewidth into SAT
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Parallel algorithms with optimal speedup for bounded treewidth
- Parameterised complexity of model checking and satisfiability in propositional dependence logic
- Canonical representations of partial 2- and 3-trees
- Mixed searching and proper-path-width
- On some tractable and hard instances for partial incentives and target set selection
- On permuted super-secondary structures of transmembrane \(\beta\)-barrel proteins
- Deleting edges to restrict the size of an epidemic in temporal networks
- Treewidth computation and extremal combinatorics
- Polynomial time algorithms for variants of graph matching on partial k-trees
- Deleting edges to restrict the size of an epidemic in temporal networks
- Searching for a Visible, Lazy Fugitive
- Shape measures of random increasing \(k\)-trees
- Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
- Approximation algorithms for treewidth
- Algorithms for recognition of regular properties and decomposition of recursive graph families
- A \(c^k n\) 5-approximation algorithm for treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Visualizing SAT instances and runs of the DPLL algorithm
- Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering
- Topological parameters for time-space tradeoff
- Treewidth lower bounds with brambles
- Understanding the scalability of Bayesian network inference using clique tree growth curves
- A branch-and-price-and-cut method for computing an optimal bramble
- On the SPANNING k-TREE problem
- Positive-instance driven dynamic programming for treewidth
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- Approximating the bandwidth for asteroidal triple-free graphs
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)
