A linear time algorithm for finding tree-decompositions of small treewidth

Cited in

(77)

Evaluating interval-valued influence diagrams
Locating Facilities on a Network to Minimize Their Average Service Radius
Learning tractable Bayesian networks in the space of elimination orders
Domino treewidth
How to use the minimal separators of a graph for its chordal triangulation
On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
Improvements to variable elimination and symbolic probabilistic inference for evaluating influence diagrams
Memory requirements for table computations in partial k-tree algorithms
A Logical Approach to Constraint Satisfaction
Kempe changes in degenerate graphs
Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs
Structural tractability of counting of solutions to conjunctive queries
A parallel algorithm for edge-coloring partial k-trees
\(k\)-NLC graphs and polynomial algorithms
Decomposition width of matroids
The birth and early years of parameterized complexity
A Linear-Time Parameterized Algorithm for Node Unique Label Cover
A basic parameterized complexity primer
Conjunctive query containment revisited
A sufficiently fast algorithm for finding close to optimal clique trees
Characterizations and algorithmic applications of chordal graph embeddings
Parallel algorithms with optimal speedup for bounded treewidth
Deleting edges to restrict the size of an epidemic in temporal networks
Deleting edges to restrict the size of an epidemic in temporal networks
Algorithms for finding f-colorings of partial k-trees
Rankings of graphs
A \(c^k n\) 5-approximation algorithm for treewidth
Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
Dynamic algorithms for graphs with treewidth 2
Shortest path queries in digraphs of small treewidth
Sequential and parallel algorithms for embedding problems on classes of partial k-trees
Capacitated domination: problem complexity and approximation algorithms
An upper bound for resolution size: characterization of tractable SAT instances
A lower bound for treewidth and its consequences
Conjunctive-query containment and constraint satisfaction
Bounds and fixed-parameter algorithms for weighted improper coloring
Efficient interprocedural data-flow analysis using treedepth and treewidth
DAG-based attack and defense modeling: don't miss the forest for the attack trees
Deleting edges to restrict the size of an epidemic: a new application for treewidth
scientific article; zbMATH DE number 7559371 (Why is no real title available?)
Deleting edges to restrict the size of an epidemic: a new application for treewidth
Recoloring graphs of treewidth 2
PTAS for Sparse General-valued CSPs
A new probabilistic constraint logic programming language based on a generalised distribution semantics
On the complexity of the regenerator location problem treewidth and other parameters
Tractability of most probable explanations in multidimensional Bayesian network classifiers
Parameterizing cut sets in a graph by the number of their components
On Imperfect Recall in Multi-Agent Influence Diagrams
On reduction algorithms for graphs with small treewidth
Bounded tree-width and LOGCFL
Improved self-reduction algorithms for graphs with bounded treewidth
Max NP-completeness made easy
On graph contractions and induced minors
Parameterized complexity of vertex splitting to pathwidth at most 1
Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
Seeing Arboretum for the (partial k-) Trees
Finding edge-disjoint paths in partial k-trees
Computing cooperative solution concepts in coalitional skill games
Space saving by dynamic algebraization based on tree-depth
The parameterised complexity of computing the maximum modularity of a graph
Small resolution proofs for QBF using dependency treewidth
Regular-factors in the complements of partial k-trees
Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1
An improved parameterized algorithm for treewidth
Optimal parametric search on graphs of bounded tree-width
Extension complexity, MSO logic, and treewidth
Channel assignment on graphs of bounded treewidth
The complexity of induced minors and related problems
Generalized coloring for tree-like graphs
Learning to integrate deduction and search in reasoning about quantified Boolean formulas
The k-separator problem: polyhedra, complexity and approximation results
Generalized dominators for structured programs
The density maximization problem in graphs
An efficient tree decomposition method for permanents and mixed discriminants
On Interval Routing Schemes and treewidth
A simple linear-time algorithm for finding path-decompositions of small width
Definability equals recognizability of partial 3-trees

This page was built for publication: A linear time algorithm for finding tree-decompositions of small treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5248490)