Showing 2013Show all
2 papers · 1 filter
cs.CC2013
One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries
Hubie Chen, Moritz Müller
We study the problem of conjunctive query evaluation relative to a class of queries; this problem is formulated here as the relational homomorphism problem relative to a class of s…
cs.CC2013
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity
Hubie Chen, Moritz Müller
We perform a fundamental investigation of the complexity of conjunctive query evaluation from the perspective of parameterized complexity. We classify sets of boolean conjunctive q…