Structural tractability of enumerating CSP solutions
From MaRDI portal
Publication:2342585
DOI10.1007/s10601-012-9129-8zbMath1310.05151arXiv1005.1567OpenAlexW3105352315WikidataQ57782841 ScholiaQ57782841MaRDI QIDQ2342585
Gianluigi Greco, Francesco Scarcello
Publication date: 29 April 2015
Published in: Constraints (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1005.1567
Trees (05C05) Hypergraphs (05C65) Enumeration in graph theory (05C30) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph designs and isomorphic decomposition (05C51)
Related Items (8)
Structural tractability of counting of solutions to conjunctive queries ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Semantic Acyclicity on Graph Databases ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ Enumerating homomorphisms ⋮ General space-time tradeoffs via relational queries ⋮ Finding a given number of solutions to a system of fuzzy constraints ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Enumerating homomorphisms
- On the finite controllability of conjunctive query answering in databases under open-world assumption
- Monadic second-order evaluations on tree-decomposable graphs
- Hypertree decompositions and tractable queries
- The complexity of counting homomorphisms seen from the other side
- Graph minors. III. Planar tree-width
- A unified theory of structural tractability for constraint satisfaction problems
- Linear delay enumeration and monadic second-order logic
- The tree projection theorem and relational query processing
- Graph minors. V. Excluding a planar graph
- Tree clustering for constraint networks
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- A comparison of structural CSP decomposition methods
- Conjunctive-query containment and constraint satisfaction
- Tractable decision for a constraint language implies tractable search
- The complexity of first-order and monadic second-order logic revisited
- Size Bounds and Query Plans for Relational Joins
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Monadic datalog over finite structures of bounded treewidth
- Enumeration of monadic second-order queries on trees
- Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight
- Counting and Enumeration Problems with Bounded Treewidth
- Generalized hypertree decompositions: NP-hardness and tractable variants
- Computing thejth solution of a first-order query
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Constraint solving via fractional edge covers
- Enumerating All Solutions for Constraint Satisfaction Problems
- On Acyclic Conjunctive Queries and Constant Delay Enumeration
- MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
- Tree-Related Widths of Graphs and Hypergraphs
- Power of Natural Semijoins
- On generating all solutions of generalized satisfiability problems
- When is the evaluation of conjunctive queries tractable?
- First-order queries on structures of bounded degree are computable with constant delay
- On the Power of k-Consistency
- Uniform Constraint Satisfaction Problems and Database Theory
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
This page was built for publication: Structural tractability of enumerating CSP solutions
