Complexity of Finding Embeddings in a k-Tree

DOI10.1137/0608024zbMath0611.05022OpenAlexW2085550081WikidataQ29013861 ScholiaQ29013861MaRDI QIDQ3751595

Stefan Arnborg, Andrzej Proskurowski, 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

zbMATH Keywords

NP completeness algorithm complexity k-tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (only showing first 100 items - show all)

Improving robustness of next-hop routing ⋮ Minimal triangulations of graphs: a survey ⋮ Safe separators for treewidth ⋮ Lex M versus MCS-M ⋮ Trees, grids, and MSO decidability: from graphs to matroids ⋮ Tractability in constraint satisfaction problems: a survey ⋮ 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 ⋮ A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ Treewidth of cocomparability graphs and a new order-theoretic parameter ⋮ Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees ⋮ A comparison of graphical techniques for decision analysis ⋮ Approximate tree decompositions of planar graphs in linear time ⋮ Approximation algorithms for treewidth ⋮ Probability propagation ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ On embedding graphs in trees ⋮ Online promise problems with online width metrics ⋮ Symbolic techniques in satisfiability solving ⋮ Tree clustering for constraint networks ⋮ Linear time algorithms for NP-hard problems restricted to partial k- trees ⋮ Treewidth for graphs with small chordality ⋮ Characterizations and algorithmic applications of chordal graph embeddings ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Achievable sets, brambles, and sparse treewidth obstructions ⋮ An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem ⋮ On treewidth and minimum fill-in of asteroidal triple-free graphs ⋮ Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ A new probabilistic constraint logic programming language based on a generalised distribution semantics ⋮ Practical algorithms for branch-decompositions of planar graphs ⋮ Decomposition width of matroids ⋮ Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models ⋮ Interval degree and bandwidth of a graph ⋮ Computing bond orders in molecule graphs ⋮ An efficient tree decomposition method for permanents and mixed discriminants ⋮ Approximating the treewidth of AT-free graphs. ⋮ Splitting a graph into disjoint induced paths or cycles. ⋮ Constant-degree graph expansions that preserve treewidth ⋮ Directed NLC-width ⋮ The dag-width of directed graphs ⋮ Forbidden minors characterization of partial 3-trees ⋮ Chordal embeddings of planar graphs ⋮ A comparison of boundary graph grammars and context-free hypergraph grammars ⋮ A logic-based analysis of Dempster-Shafer theory ⋮ Faster computation of the Robinson-Foulds distance between phylogenetic networks ⋮ On the extension of a partial metric to a tree metric ⋮ Treewidth governs the complexity of target set selection ⋮ PRM inference using Jaffray \& Faÿ's local conditioning ⋮ Treewidth lower bounds with brambles ⋮ Maximum \(k\)-splittable \(s, t\)-flows ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Monotonicity of non-deterministic graph searching ⋮ An annotated bibliography on guaranteed graph searching ⋮ Distributed chasing of network intruders ⋮ Approximation algorithms for digraph width parameters ⋮ Algorithms for recognition of regular properties and decomposition of recursive graph families ⋮ The complexity of minimum-length path decompositions ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families ⋮ 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 ⋮ Canonical representations of partial 2- and 3-trees ⋮ \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions ⋮ Monadic second-order evaluations on tree-decomposable graphs ⋮ Precoloring extension. I: Interval graphs ⋮ On the SPANNING \(k\)-TREE problem ⋮ On the complexity of finding iso- and other morphisms for partial \(k\)- trees ⋮ Efficient computation of the characteristic polynomial of a tree and related tasks ⋮ Studies on hypergraphs. I: Hyperforests ⋮ Complexity of path-forming games ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time ⋮ Treewidth and minimum fill-in on permutation graphs in linear time ⋮ Exact and approximate bandwidth ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Understanding the scalability of Bayesian network inference using clique tree growth curves ⋮ Complexity of secure sets ⋮ Perspectives on the theory and practice of belief functions ⋮ All structured programs have small tree width and good register allocation ⋮ Upper bounds on the size of obstructions and intertwines ⋮ Nondeterministic graph searching: from pathwidth to treewidth ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Computational properties of argument systems satisfying graph-theoretic constraints ⋮ Triangulating graphs with few \(P_4\)'s ⋮ Conjunctive query containment revisited ⋮ Edge and node searching problems on trees ⋮ A faster tree-decomposition based algorithm for counting linear extensions ⋮ On hyperedge replacement and BNLC graph grammars ⋮ On the pathwidth of chordal graphs ⋮ On some optimization problems on \(k\)-trees and partial \(k\)-trees ⋮ Counting \(H-\)colorings of partial \(k-\)trees ⋮ Listing all potential maximal cliques of a graph ⋮ Minimal acyclic forbidden minors for the family of graphs with bounded path-width ⋮ Hybrid backtracking bounded by tree-decomposition of constraint networks

Cites Work

This page was built for publication: Complexity of Finding Embeddings in a k-Tree