Complexity of Finding Embeddings in a k-Tree
From MaRDI portal
Publication:3751595
DOI10.1137/0608024zbMATH Open0611.05022OpenAlexW2085550081WikidataQ29013861 ScholiaQ29013861MaRDI QIDQ3751595FDOQ3751595
Authors: 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
Recommendations
- scientific article
- 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
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?)
- Graph theory with applications
- 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)
- The monadic second-order logic of graphs : Definable sets of finite graphs
- Treewidth and gonality of glued grid graphs
- On hyperedge replacement and BNLC graph grammars
- On strict brambles
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- The nonexistence of reduction rules giving an embedding into a \(k\)-tree
- Postoptimal Analysis in Nonserial Dynamic Programming
- Graph searching on chordal graphs
- Faster computation of path-width
- Digraphs of bounded width
- Minimum size tree-decompositions
- Triangulating graphs with few \(P_4\)'s
- On the impact of treewidth in the computational complexity of freezing dynamics
- Digraphs of bounded elimination width
- Combining restarts, nogoods and bag-connected decompositions for solving csps
- Linear-time minimal cograph editing
- Hybrid backtracking bounded by tree-decomposition of constraint networks
- Revising Johnson's table for the 21st century
- Chordal networks of polynomial ideals
- Positive-instance driven dynamic programming for treewidth
- Maximum \(k\)-splittable \(s, t\)-flows
- Graphical Models and Message-Passing Algorithms: Some Introductory Lectures
- Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
- Faster and enhanced inclusion-minimal cograph completion
- Computational aspects of treewidth for graph
- Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
- Lex M versus MCS-M
- Trees, grids, and MSO decidability: from graphs to matroids
- Learning tractable Bayesian networks in the space of elimination orders
- Turbocharging treewidth heuristics
- Approximating Pathwidth for Graphs of Small Treewidth
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Theory of evidence ? A survey of its mathematical foundations, applications and computational aspects
- A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
- On the hardness of palletizing bins using FIFO queues
- 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
- Treewidth, crushing and hyperbolic volume
- Symbolic techniques in satisfiability solving
- Tree decomposition and discrete optimization problems: a survey
- A comparison of graphical techniques for decision analysis
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- Title not available (Why is that?)
- Approximating the treewidth of AT-free graphs.
- On tradeoffs between width- and fill-like graph parameters
- Inference in belief networks: A procedural guide
- Tree-decompositions of small pathwidth
- The power of non-ground rules in Answer Set Programming
- Parameterised complexity of model checking and satisfiability in propositional dependence logic
- Encoding Treewidth into SAT
- On permuted super-secondary structures of transmembrane \(\beta\)-barrel proteins
- On some tractable and hard instances for partial incentives and target set selection
- Visualizing SAT instances and runs of the DPLL algorithm
- Approximating the bandwidth for asteroidal triple-free graphs
- Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering
- Positive-instance driven dynamic programming for treewidth
- A branch-and-price-and-cut method for computing an optimal bramble
- Understanding the scalability of Bayesian network inference using clique tree growth curves
- Sequential and parallel algorithms for embedding problems on classes of partial k-trees
- Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
- Online promise problems with online width metrics
- A linear fixed parameter tractable algorithm for connected pathwidth
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- Interval degree and bandwidth of a graph
- Treewidth distance on phylogenetic trees
- Weighted Treewidth Algorithmic Techniques and Results
- A lower bound for treewidth and its consequences
- On the complexity of computing treebreadth
- On the complexity of computing treebreadth
- Dependence modelling in ultra high dimensions with vine copulas and the graphical Lasso
- On the complexity of planning for agent teams and its implications for single agent planning
- Two feedback problems for graphs with bounded tree-width
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Computing Tree Decompositions
- Comparing linear width parameters for directed graphs
- Exact algorithms for a discrete metric labeling problem
- Tangle bases: Revisited
- On the \(k\)-rainbow domination in graphs with bounded tree-width
- Integrating and sampling cuts in bounded treewidth graphs
- Treewidth of the generalized Kneser graphs
- Optimal one-page tree embeddings in linear time
- Finding all leftmost separators of size \(\le k\)
- Equitable list tree-coloring of bounded treewidth graphs
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- Minimum size tree-decompositions
- On the maximum weight minimal separator
- Finding good tree decompositions by local search
- A parameterized view on the complexity of dependence logic
- Path cover problems with length cost
- NC-algorithms for graphs with small treewidth
- Complete-subgraph-transversal-sets problem on bounded treewidth graphs
- Using a hybrid of exact and genetic algorithms to design survivable networks
- Solving frequency assignment problems via tree-decomposition
- Minimum fill-in: inapproximability and almost tight lower bounds
- Canonical representations of partial 2-and 3-trees
- Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
- Title not available (Why is that?)
- A new probabilistic constraint logic programming language based on a generalised distribution semantics
- Practical algorithms for branch-decompositions of planar graphs
- Probabilistic and exact frequent subtree mining in graphs beyond forests
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)
