Complexity of Finding Embeddings in a k-Tree
From MaRDI portal
Publication:3751595
DOI10.1137/0608024zbMath0611.05022WikidataQ29013861 ScholiaQ29013861MaRDI QIDQ3751595
Andrzej Proskurowski, Stefan Arnborg, Derek Gordon Corneil
Publication date: 1987
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0608024
68Q25: Analysis of algorithms and problem complexity
90C39: Dynamic programming
05C10: Planar graphs; geometric and topological aspects of graph theory
Related Items
Graph decompositions and tree automata in reasoning with uncertainty, Theory of evidence ? A survey of its mathematical foundations, applications and computational aspects, A sufficiently fast algorithm for finding close to optimal clique trees, Topological parameters for time-space tradeoff, Using a hybrid of exact and genetic algorithms to design survivable networks, Tree-decompositions of small pathwidth, Algorithmic uses of the Feferman-Vaught theorem, The complexity of subgraph isomorphism for classes of partial k-trees, Characterization and complexity of uniformly nonprimitive labeled 2-structures, The complexity of pursuit on a graph, Mixed searching and proper-path-width, Monadic second-order evaluations on tree-decomposable graphs, On the SPANNING \(k\)-TREE problem, 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., 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, Domination and total domination on asteroidal triple-free graphs, A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs, Unnamed Item, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
