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; 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
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)
- 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
- Learning bounded tree-width Bayesian networks via sampling
- 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
- Deleting edges to restrict the size of an epidemic in temporal networks
- Polynomial time algorithms for variants of graph matching on partial \(k\)-trees
- Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
- Approximation algorithms for treewidth
- Algorithms for recognition of regular properties and decomposition of recursive graph families
- A partial k-arboretum of graphs with bounded treewidth
- Fifty years of the spectrum problem: survey and new results
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- On the SPANNING \(k\)-TREE problem
- Treewidth for graphs with small chordality
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Triangulating graphs without asteroidal triples
- Chordal embeddings of planar graphs
- Minimal triangulations of graphs: a survey
- On the extension of a partial metric to a tree metric
- Approximate tree decompositions of planar graphs in linear time
- Propositional semantics for disjunctive logic programs
- Approximate tree decompositions of planar graphs in linear time
- Power Indices in Spanning Connectivity Games
- Directed tree-width
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Complexity of secure sets
- On some optimization problems on \(k\)-trees and partial \(k\)-trees
- Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
- Monotonicity of non-deterministic graph searching
- Line graphs of bounded clique-width
- An extended tree-width notion for directed graphs related to the computation of permanents
- An extended tree-width notion for directed graphs related to the computation of permanents
- Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
- On the pathwidth of chordal graphs
- Splitting a graph into disjoint induced paths or cycles.
- Minimal acyclic forbidden minors for the family of graphs with bounded path-width
- Perspectives on the theory and practice of belief functions
- Treewidth of cocomparability graphs and a new order-theoretic parameter
- Efficient learning of Bayesian networks with bounded tree-width
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Linear layouts measuring neighbourhoods in graphs
- The pathwidth and treewidth of cographs
- Listing all potential maximal cliques of a graph
- Monadic second-order evaluations on tree-decomposable graphs
- Title not available (Why is that?)
- Tree clustering for constraint networks
- Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
- Tree decompositions with small cost
- Parameterized complexity of vertex colouring
- Computational properties of argument systems satisfying graph-theoretic constraints
- Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
- Domination and total domination on asteroidal triple-free graphs
- On embedding graphs in trees
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- To approximate treewidth, use treelength!
- Exact and approximate bandwidth
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Forbidden minors characterization of partial 3-trees
- Distributed chasing of network intruders
- Nondeterministic graph searching: from pathwidth to treewidth
- An improved algorithm for finding tree decompositions of small width
- Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
- Bounded-width QBF is PSPACE-complete
- The Space Complexity of k-Tree Isomorphism
- Fixed-parameter tractability of treewidth and pathwidth
- Methods for solving reasoning problems in abstract argumentation -- a survey
- Two strikes against perfect phylogeny
- 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
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)
