A linear time algorithm for finding tree-decompositions of small treewidth
From MaRDI portal
Publication:5248490
DOI10.1145/167088.167161zbMATH Open1310.05194DBLPconf/stoc/Bodlaender93OpenAlexW2024291212WikidataQ59568000 ScholiaQ59568000MaRDI QIDQ5248490FDOQ5248490
Authors: Hans L. Bodlaender 
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
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph minors (05C83)
Cited In (77)
- Domino treewidth
- Kempe changes in degenerate graphs
- A parallel algorithm for edge-coloring partial k-trees
- A Linear-Time Parameterized Algorithm for Node Unique Label Cover
- Efficient interprocedural data-flow analysis using treedepth and treewidth
- PTAS for Sparse General-valued CSPs
- On Imperfect Recall in Multi-Agent Influence Diagrams
- Parameterized complexity of vertex splitting to pathwidth at most 1
- Seeing Arboretum for the (partial k-) Trees
- 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
- Generalized dominators for structured programs
- On Interval Routing Schemes and treewidth
- Definability equals recognizability of partial 3-trees
- Learning tractable Bayesian networks in the space of elimination orders
- How to use the minimal separators of a graph for its chordal triangulation
- Improvements to variable elimination and symbolic probabilistic inference for evaluating influence diagrams
- Memory requirements for table computations in partial k-tree algorithms
- On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
- A Logical Approach to Constraint Satisfaction
- Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs
- Structural tractability of counting of solutions to conjunctive queries
- \(k\)-NLC graphs and polynomial algorithms
- Decomposition width of matroids
- The birth and early years of parameterized complexity
- A sufficiently fast algorithm for finding close to optimal clique trees
- A basic parameterized complexity primer
- Parallel algorithms with optimal speedup for bounded treewidth
- Conjunctive query containment revisited
- Characterizations and algorithmic applications of chordal graph embeddings
- Algorithms for finding f-colorings of partial k-trees
- Deleting edges to restrict the size of an epidemic in temporal networks
- Deleting edges to restrict the size of an epidemic in temporal networks
- 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
- A lower bound for treewidth and its consequences
- An upper bound for resolution size: characterization of tractable SAT instances
- Conjunctive-query containment and constraint satisfaction
- Bounds and fixed-parameter algorithms for weighted improper coloring
- Title not available (Why is that?)
- 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
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Recoloring graphs of treewidth 2
- 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
- On reduction algorithms for graphs with small treewidth
- Bounded tree-width and LOGCFL
- Parameterizing cut sets in a graph by the number of their components
- Finding edge-disjoint paths in partial k-trees
- Max NP-completeness made easy
- Improved self-reduction algorithms for graphs with bounded treewidth
- Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
- On graph contractions and induced minors
- Space saving by dynamic algebraization based on tree-depth
- Computing cooperative solution concepts in coalitional skill games
- The parameterised complexity of computing the maximum modularity of a graph
- Small resolution proofs for QBF using dependency treewidth
- 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
- The density maximization problem in graphs
- An efficient tree decomposition method for permanents and mixed discriminants
- A simple linear-time algorithm for finding path-decompositions of small width
- Locating Facilities on a Network to Minimize Their Average Service Radius
- Evaluating interval-valued influence diagrams
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)
