Bounded Tree-Width and CSP-Related Problems
DOI10.1007/978-3-540-77120-3_55zbMATH Open1193.68130OpenAlexW1872146596MaRDI QIDQ5387797FDOQ5387797
Authors: Tommy Färnqvist, Peter Jonsson 
Publication date: 27 May 2008
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_55
Recommendations
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- On the algebraic structure of combinatorial problems
- Quickly excluding a planar graph
- Conjunctive-query containment and constraint satisfaction
- Complexity of conservative constraint satisfaction problems
- Title not available (Why is that?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Full Constraint Satisfaction Problems
- The complexity of counting homomorphisms seen from the other side
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- The approximability of constraint satisfaction problems
- Title not available (Why is that?)
- List homomorphisms and circular arc graphs
- List homomorphisms to reflexive graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- The Parameterized Complexity of Counting Problems
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- Title not available (Why is that?)
- List homomorphisms of graphs with bounded degrees
- Level of repair analysis and minimum cost homomorphisms of graphs
- Generalised Integer Programming Based on Logically Defined Relations
Cited In (16)
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
- Counting and Enumeration Problems with Bounded Treewidth
- Constraint satisfaction with bounded treewidth revisited
- Balancing Bounded Treewidth Circuits
- Can you beat treewidth?
- The smallest hard trees
- Answer set solving with bounded treewidth revisited
- Lower Bounds for QBFs of Bounded Treewidth
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Balancing bounded treewidth circuits
- The parameterised complexity of list problems on graphs of bounded treewidth
- On planar valued CSPs
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- Obstructions to partitions of chordal graphs
This page was built for publication: Bounded Tree-Width and CSP-Related Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387797)
