Complexity of Finding Embeddings in a k-Tree
From MaRDI portal
Publication:3751595
DOI10.1137/0608024zbMATH Open0611.05022OpenAlexW2085550081WikidataQ29013861 ScholiaQ29013861MaRDI QIDQ3751595FDOQ3751595
Stefan Arnborg, Andrzej Proskurowski, Derek G. 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
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- A Characterization of Comparability Graphs and of Interval Graphs
- On simple characterizations of k-trees
- Triangulated graphs and the elimination process
- Steiner trees, partial 2–trees, and minimum IFI networks
- Networks immune to isolated failures
- Characterization and Recognition of Partial 3-Trees
- Computing the Minimum Fill-In is NP-Complete
- Title not available (Why is that?)
- Separating subgraphs in k-trees: Cables and caterpillars
- A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
- Networks immune to isolated line failures
- Reduced State EnumerationߞAnother Algorithm for Reliability Evaluation
Cited In (only showing first 100 items - show all)
- Directed NLC-width
- How to use the minimal separators of a graph for its chordal triangulation
- A logic-based analysis of Dempster-Shafer theory
- Upper bounds on the size of obstructions and intertwines
- Heuristic and metaheuristic methods for computing graph treewidth
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Algorithmic uses of the Feferman-Vaught theorem
- Inference in belief networks: A procedural guide
- Complexity of path-forming games
- Decomposition width of matroids
- Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models
- Safe separators for treewidth
- Constant-degree graph expansions that preserve treewidth
- Searching for a Visible, Lazy Fugitive
- Canonical representations of partial 2- and 3-trees
- Mixed searching and proper-path-width
- Topological parameters for time-space tradeoff
- A \(c^k n\) 5-approximation algorithm for treewidth
- Treewidth lower bounds with brambles
- Tree-decompositions of small pathwidth
- The complexity of graph languages generated by hyperedge replacement
- Achievable sets, brambles, and sparse treewidth obstructions
- Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$
- Minimal separators in extended \(P_4\)-laden graphs
- Edge and node searching problems on trees
- Faster computation of the Robinson-Foulds distance between phylogenetic networks
- Computing the branchwidth of interval graphs
- A comparison of boundary graph grammars and context-free hypergraph grammars
- Binary join trees for computing marginals in the Shenoy-Shafer architecture
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- The three-in-a-tree problem
- The complexity of subgraph isomorphism for classes of partial k-trees
- Efficient pattern matching on graph patterns of bounded treewidth
- Tractability of most probable explanations in multidimensional Bayesian network classifiers
- A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions
- Bounded tree-width and LOGCFL
- Counting \(H-\)colorings of partial \(k-\)trees
- An Experimental Study of the Treewidth of Real-World Graph Data
- Independent sets in asteroidal triple-free graphs
- Approximation algorithms for digraph width parameters
- Node-searching problem on block graphs
- The basic algorithm for pseudo-Boolean programming revisited
- Studies on hypergraphs. I: Hyperforests
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- How to compute digraph width measures on directed co-graphs
- Title not available (Why is that?)
- Treewidth and pathwidth of permutation graphs
- Recoloring graphs via tree decompositions
- All structured programs have small tree width and good register allocation
- The complexity of minimum-length path decompositions
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- Degree-constrained decompositions of graphs: Bounded treewidth and planarity
- A faster tree-decomposition based algorithm for counting linear extensions
- Tree-width, path-width, and cutwidth
- Computing bond orders in molecule graphs
- On the tree-width of planar graphs
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Regularity and locality in \(k\)-terminal graphs
- Computing partial hypergraphs of bounded width
- Parameters Tied to Treewidth
- Efficient computation of the characteristic polynomial of a tree and related tasks
- Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth
- \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
- An implementation of the iterative proportional fitting procedure by propagation trees.
- Algorithms and complexity for Turaev-Viro invariants
- An efficient tree decomposition method for permanents and mixed discriminants
- PRM inference using Jaffray \& Faÿ's local conditioning
- Characterization and complexity of uniformly nonprimitive labeled 2-structures
- Tree-decompositions with bags of small diameter
- Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
- An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
- The parametrized complexity of knot polynomials
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Probability propagation
- The complexity of pursuit on a graph
- Improving robustness of next-hop routing
- Treewidth and minimum fill-in on permutation graphs in linear time
- Precoloring extension. I: Interval graphs
- A Logical Approach to Constraint Satisfaction
- An exact method for graph coloring
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Lpopt: a rule optimization tool for answer set programming
- On sparsification for computing treewidth
- The dag-width of directed graphs
- Treewidth governs the complexity of target set selection
- Tractability in constraint satisfaction problems: a survey
- Constructive linear time algorithms for branchwidth
- \(k\)-NLC graphs and polynomial algorithms
- Courcelle's theorem -- a game-theoretic approach
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- A sufficiently fast algorithm for finding close to optimal clique trees
- Parallel algorithms with optimal speedup for bounded treewidth
- Conjunctive query containment revisited
- Characterizations and algorithmic applications of chordal graph embeddings
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Deleting edges to restrict the size of an epidemic in temporal networks
- An annotated bibliography on guaranteed graph searching
- Treewidth computation and extremal combinatorics
- Polynomial time algorithms for variants of graph matching on partial \(k\)-trees
- Fixed-Parameter Tractability of Treewidth and Pathwidth
Recommendations
- Title not available (Why is that?) 👍 👎
- Sequential and parallel algorithms for embedding problems on classes of partial k-trees 👍 👎
- Title not available (Why is that?) 👍 👎
- 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 👍 👎
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)
