Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
DOI10.1016/j.jcss.2017.11.005zbMath1390.68345arXiv1711.05216MaRDI QIDQ1745716
Georg Gottlob, Francesco Scarcello, Gianluigi Greco
Publication date: 18 April 2018
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.05216
database theory; optimization problems; constraint satisfaction problems; conjunctive queries; query optimization; structural decomposition methods; AI; tree projections; parallel models of computation
68Q25: Analysis of algorithms and problem complexity
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68R10: Graph theory (including graph drawing) in computer science
90C27: Combinatorial optimization
68W10: Parallel algorithms in computer science
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- Enumerating homomorphisms
- A bridging model for multi-core computing
- Hypertree decompositions and tractable queries
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- Hybrid backtracking bounded by tree-decomposition of constraint networks
- Arc consistency for soft constraints
- High-order consistency in valued constraint satisfaction
- A unified theory of structural tractability for constraint satisfaction problems
- Soft arc consistency revisited
- On the power of structural decompositions of graph-based representations of constraint problems
- The tree projection theorem and relational query processing
- Tree clustering for constraint networks
- A comparison of structural CSP decomposition methods
- Conjunctive-query containment and constraint satisfaction
- Binary vs. non-binary constraints
- Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
- Networks of constraints: Fundamental properties and applications to picture processing
- Structural tractability of enumerating CSP solutions
- Unifying tree decompositions for reasoning in graphical models
- On the parallel complexity of discrete relaxation in constraint satisfaction networks
- Searching for the M Best Solutions in Graphical Models
- Approximating fractional hypertree width
- On the Desirability of Acyclic Database Schemes
- Degrees of acyclicity for hypergraphs and relational database schemes
- The complexity of acyclic conjunctive queries
- Generalized hypertree decompositions: NP-hardness and tractable variants
- Query evaluation via tree-decompositions
- 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
- Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
- On the complexity of join dependencies
- Graph minors. II. Algorithmic aspects of tree-width
- Power of Natural Semijoins
- A simplied universal relation assumption and its properties
- Semiring-based constraint satisfaction and optimization
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- Principles and Practice of Constraint Programming – CP 2003
- Computing LOGCFL certificates
