A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
From MaRDI portal
Publication:5738928
DOI10.4230/LIPIcs.ICDT.2015.110zbMath1365.68199arXiv1408.0890OpenAlexW2963348585MaRDI QIDQ5738928
Publication date: 13 June 2017
Full work available at URL: https://arxiv.org/abs/1408.0890
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (10)
Unnamed Item ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ The smallest hard trees ⋮ Answer Counting under Guarded TGDs ⋮ Solving projected model counting by utilizing treewidth and its limits ⋮ Unnamed Item ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Parameterised complexity of model checking and satisfiability in propositional dependence logic ⋮ Counting Answers to Existential Questions ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
This page was built for publication: A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
