Fetching the paper…
Reading the bibliography…
The problem of deciding whether CSP instances admit solutions has been deeply studied in the literature, and several structural tractability results have been derived so far.
The power of natural semijoins
P.A. Bernstein and N. Goodman · 1981
Earlier work this paper cites.
The tree projection theorem and relational query processing
N. Goodman and O. Shmueli · 1984
Earlier work this paper cites.
Graph minors III: Planar tree-width
N. Robertson and P.D. Seymour · 1984
Earlier work this paper cites.
Graph minors V: Excluding a planar graph
N. Robertson and P.D. Seymour · 1986
Earlier work this paper cites.
R. Dechter and A. Itai. Finding All Solutions if You can Find One. In Proc. of AAAI-92 Workshop on Tractable Reasoning , pp. 35–39, 1992
1992
Earlier work this paper cites.
Solving Queries by Tree Projections
Y. Sagiv and O Shmueli · 1993
Earlier work this paper cites.
Parameterized Complexity
R.G. Downey and M.R. Fellows · 1999
Earlier work this paper cites.
G. Gottlob, N. Leone, and F. Scarcello. A Comparison of Structural CSP Decomposition Methods. Artificial Intelligence , 124(2): 243–282, 2000
2000
Earlier work this paper cites.
When is the evaluation of conjunctive queries tractable?
M. Grohe, T. Schwentick, and L. Segoufin · 2001
Cited alongside, same era.
Hypertree decompositions and tractable queries
G. Gottlob, N. Leone, and F. Scarcello · 2002
Cited alongside, same era.
Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width
G. Gottlob, N. Leone, and F. Scarcello · 2003
Cited alongside, same era.
D.A. Cohen. Tractable Decision for a Constraint Language Implies Tractable Search. Constraints , 9(3), 219–229, 2004
2004
Cited alongside, same era.
Beyond Hypertree Width: Decomposition Methods Without Decompositions
H. Chen and V. Dalmau · 2005
Cited alongside, same era.
M. Grohe and D. Marx. Constraint solving via fractional edge covers. In Proc. of SODA’06 , pp. 289–298, 2006
The complexity of homomorphism and constraint satisfaction problems seen from the other side
M. Grohe · 2007
Later among the works it cites.
Tree-Related Widths of Graphs and Hypergraphs
I. Adler · 2008
Later among the works it cites.
D. Cohen, P. Jeavons, and M. Gyssens. A unified theory of structural tractability for constraint satisfaction problems. Journal of Computer and System Sciences , 74(5): 721-743, 2008
2008
Later among the works it cites.
Approximating fractional hypertree width
D. Marx · 2008
Later among the works it cites.
Uniform Constraint Satisfaction Problems and Database Theory
F. Scarcello, G. Gottlob, and G. Greco · 2008
Later among the works it cites.
A. Bulatov, V. Dalmau, M. Grohe, and D. Marx. Enumerating Homomorphism. In Proc. of STACS’09 , pp. 231–242, 2009
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2006
Cited alongside, same era.
On the Power of k-Consistency,
A. Atserias, A. Bulatov, and V. Dalmau · 2007
Cited alongside, same era.
The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability
G. Greco and F. Scarcello
Cited in the paper.
D. Marx. Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries. To appear in Proc. of STOC’10
Cited in the paper.
2009
Later among the works it cites.
Generalized hypertree decompositions: NP
G. Gottlob, Z. Miklós, and T. Schwentick · 2009
Later among the works it cites.