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
- 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
- scientific article; zbMATH DE number 3884101 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 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)- Optimal one-page tree embeddings in linear time
- Nondeterministic graph searching: from pathwidth to treewidth
- Computational properties of argument systems satisfying graph-theoretic constraints
- On embedding graphs in trees
- Tree clustering for constraint networks
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Algorithms for recognition of regular properties and decomposition of recursive graph families
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Canonical representations of partial 2- and 3-trees
- Precoloring extension. I: Interval graphs
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Studies on hypergraphs. I: Hyperforests
- Complexity of path-forming games
- All structured programs have small tree width and good register allocation
- Upper bounds on the size of obstructions and intertwines
- A partial k-arboretum of graphs with bounded treewidth
- Triangulating graphs with few \(P_4\)'s
- On hyperedge replacement and BNLC graph grammars
- On the pathwidth of chordal graphs
- On some optimization problems on \(k\)-trees and partial \(k\)-trees
- Minimal acyclic forbidden minors for the family of graphs with bounded path-width
- A review of combinatorial problems arising in feedforward neural network design
- Improved self-reduction algorithms for graphs with bounded treewidth
- The nonexistence of reduction rules giving an embedding into a \(k\)-tree
- Regularity and locality in \(k\)-terminal graphs
- \(k\)-NLC graphs and polynomial algorithms
- Treewidth of cocomparability graphs and a new order-theoretic parameter
- A comparison of graphical techniques for decision analysis
- Probability propagation
- Treewidth for graphs with small chordality
- Characterizations and algorithmic applications of chordal graph embeddings
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Interval degree and bandwidth of a graph
- Approximating the treewidth of AT-free graphs.
- Splitting a graph into disjoint induced paths or cycles.
- Chordal embeddings of planar graphs
- On the extension of a partial metric to a tree metric
- Conjunctive query containment revisited
- Edge and node searching problems on trees
- Counting \(H-\)colorings of partial \(k-\)trees
- Listing all potential maximal cliques of a graph
- An implementation of the iterative proportional fitting procedure by propagation trees.
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Treewidth distance on phylogenetic trees
- Probabilistic reasoning with graphical security models
- Recoloring graphs via tree decompositions
- Polynomial time algorithms for variants of graph matching on partial k-trees
- Combining restarts, nogoods and bag-connected decompositions for solving csps
- Turbocharging treewidth heuristics
- Tractability of most probable explanations in multidimensional Bayesian network classifiers
- A branch-and-price-and-cut method for computing an optimal bramble
- Minimal separators in extended \(P_4\)-laden graphs
- Two feedback problems for graphs with bounded tree-width
- Tree decompositions with small cost
- Computing the branchwidth of interval graphs
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- Tree-width, path-width, and cutwidth
- Inference in belief networks: A procedural guide
- Binary join trees for computing marginals in the Shenoy-Shafer architecture
- Parameterized complexity of vertex colouring
- Directed tree-width
- The parametrized complexity of knot polynomials
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Triangulating graphs without asteroidal triples
- Propositional semantics for disjunctive logic programs
- Improved Steiner tree algorithms for bounded treewidth
- Domination and total domination on asteroidal triple-free graphs
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Efficiently enumerating minimal triangulations
- On the complexity of computing treebreadth
- On tradeoffs between width- and fill-like graph parameters
- On some tractable and hard instances for partial incentives and target set selection
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- Complete-subgraph-transversal-sets problem on bounded treewidth graphs
- Revising Johnson's table for the 21st century
- On the impact of treewidth in the computational complexity of freezing dynamics
- New limits of treewidth-based tractability in optimization
- Treewidth of the generalized Kneser graphs
- Linear-time minimal cograph editing
- Finding all leftmost separators of size \(\le k\)
- A parameterized view on the complexity of dependence logic
- Path cover problems with length cost
- On quasi-planar graphs: clique-width and logical description
- Treewidth and gonality of glued grid graphs
- Chordal graphs in triangular decomposition in top-down style
- A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
- Equitable list tree-coloring of bounded treewidth graphs
- How to compute digraph width measures on directed co-graphs
- On efficiently solvable cases of quantum \(k\)-SAT
- An improvement of Reed's treewidth approximation
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- An extended tree-width notion for directed graphs related to the computation of permanents
- The basic algorithm for pseudo-Boolean programming revisited
- The complexity of graph languages generated by hyperedge replacement
- Treewidth, crushing and hyperbolic volume
- Variable neighborhood search for graphical model energy minimization
- Minimum fill-in: inapproximability and almost tight lower bounds
- Algorithms and complexity for Turaev-Viro invariants
- Learning tractable Bayesian networks in the space of elimination orders
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)
