The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space

DOI10.1145/2751316zbMath1347.68179arXiv1306.5424OpenAlexW2260560831MaRDI QIDQ2828230

Hubie Chen, Moritz Müller

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.5424

zbMATH Keywords

conjunctive queriesgraph decompositionshomomorphism problemsparameterized logarithmic space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Unnamed Item ⋮ The parameterized space complexity of embedding along a path ⋮ Parameterised counting in logspace ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Parameterised complexity of model checking and satisfiability in propositional dependence logic ⋮ On the Descriptive Complexity of Color Coding

This page was built for publication: The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space