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

Cited in

(88)

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

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)