A linear time algorithm for finding tree-decompositions of small treewidth
From MaRDI portal
Publication:5248490
DOI10.1145/167088.167161zbMath1310.05194OpenAlexW2024291212WikidataQ59568000 ScholiaQ59568000MaRDI QIDQ5248490
Publication date: 7 May 2015
Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)
Full work available at URL: https://dspace.library.uu.nl/handle/1874/16670
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (73)
Structural tractability of counting of solutions to conjunctive queries ⋮ Seeing Arboretum for the (partial k-) Trees ⋮ Improved self-reduction algorithms for graphs with bounded treewidth ⋮ \(k\)-NLC graphs and polynomial algorithms ⋮ Evaluating interval-valued influence diagrams ⋮ Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ 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 ⋮ The complexity of induced minors and related problems ⋮ Optimal parametric search on graphs of bounded tree-width ⋮ Regular-factors in the complements of partial k-trees ⋮ The Birth and Early Years of Parameterized Complexity ⋮ A Basic Parameterized Complexity Primer ⋮ Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ Generalized coloring for tree-like graphs ⋮ Characterizations and algorithmic applications of chordal graph embeddings ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ Small Resolution Proofs for QBF using Dependency Treewidth ⋮ The density maximization problem in graphs ⋮ Secluded connectivity problems ⋮ Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ 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 ⋮ On Interval Routing Schemes and treewidth ⋮ On graph contractions and induced minors ⋮ Decomposition width of matroids ⋮ 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 ⋮ An efficient tree decomposition method for permanents and mixed discriminants ⋮ Channel assignment on graphs of bounded treewidth ⋮ Unnamed Item ⋮ An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances ⋮ Max NP-completeness made easy ⋮ Parameterizing cut sets in a graph by the number of their components ⋮ Tractability of most probable explanations in multidimensional Bayesian network classifiers ⋮ DAG-based attack and defense modeling: don't miss the forest for the attack trees ⋮ Locating Facilities on a Network to Minimize Their Average Service Radius ⋮ Recoloring graphs of treewidth 2 ⋮ Computing cooperative solution concepts in coalitional skill games ⋮ Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time ⋮ A simple linear-time algorithm for finding path-decompositions of small width ⋮ 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 ⋮ Generalized dominators for structured programs ⋮ A sufficiently fast algorithm for finding close to optimal clique trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ Improvements to variable elimination and symbolic probabilistic inference for evaluating influence diagrams ⋮ Bounds and fixed-parameter algorithms for weighted improper coloring ⋮ Parameterized Complexity of Discrete Morse Theory ⋮ Learning tractable Bayesian networks in the space of elimination orders ⋮ Learning to Integrate Deduction and Search in Reasoning about Quantified Boolean Formulas ⋮ Conjunctive query containment revisited ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ The parameterised complexity of computing the maximum modularity of a graph ⋮ A Logical Approach to Constraint Satisfaction ⋮ Conjunctive-query containment and constraint satisfaction ⋮ Capacitated domination: problem complexity and approximation algorithms ⋮ Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results
This page was built for publication: A linear time algorithm for finding tree-decompositions of small treewidth
