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