Hypertree decompositions and tractable queries
From MaRDI portal
(Redirected from Publication:696962)
Recommendations
Cites work
- scientific article; zbMATH DE number 3571498 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1142309 (Why is no real title available?)
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A comparison of structural CSP decomposition methods
- A complexity theory based on Boolean algebra
- A simplied universal relation assumption and its properties
- A sufficient condition for backtrack-bounded search
- Alternation
- Closure properties of constraints
- Computing LOGCFL certificates
- Conjunctive-query containment and constraint satisfaction
- Constraint satisfaction from a deductive viewpoint
- Decomposing constraint satisfaction problems using database techniques
- Degrees of acyclicity for hypergraphs and relational database schemes
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Graph minors. II. Algorithmic aspects of tree-width
- On Determining Tree Query Membership Of A Distributed Query
- On the Desirability of Acyclic Database Schemes
- Power of Natural Semijoins
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- The Hardest Context-Free Language
- The complexity of acyclic conjunctive queries
- The well-founded semantics for general logic programs
- Tree clustering for constraint networks
- Tree queries
- Tree-size bounded alternation
Cited in
(81)- Computational complexity of auditing finite attributes in statistical databases
- The complexity of weighted counting for acyclic conjunctive queries
- Domain permutation reduction for constraint satisfaction problems
- On minimal constraint networks
- Structural tractability of counting of solutions to conjunctive queries
- Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
- Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
- Structural decompositions for problems with global constraints
- Tractability in constraint satisfaction problems: a survey
- A negative conjunctive query is easy if and only if it is beta-acyclic
- A backtracking-based algorithm for hypertree decomposition
- scientific article; zbMATH DE number 2080462 (Why is no real title available?)
- Dynamic Management of Heuristics for Solving Structured CSPs
- A Logical Approach to Constraint Satisfaction
- On the power of structural decompositions of graph-based representations of constraint problems
- A more general theory of static approximations for conjunctive queries
- Tractable structures for constraint satisfaction with truth tables
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- Computing hypergraph width measures exactly
- Connectivity and equilibrium in random games
- A more general theory of static approximations for conjunctive queries
- Fast and parallel decomposition of constraint satisfaction problems
- Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
- Constraint satisfaction with bounded treewidth revisited
- scientific article; zbMATH DE number 1834638 (Why is no real title available?)
- Coalition structure generation: a survey
- Weighted hypertree decompositions and optimal query plans
- Constraint satisfaction with succinctly specified relations
- Generalized hypertree decompositions: NP-hardness and tractable variants
- HyperBench. A benchmark and tool for hypergraphs and empirical findings
- Backdoors into heterogeneous classes of SAT and CSP
- Combined tractability of query evaluation via tree automata and cycluits
- Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT
- Generic local computation
- Query evaluation via tree-decompositions
- Semantic acyclicity on graph databases
- A comparison of structural CSP decomposition methods
- Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- Between tree patterns and conjunctive queries: is there tractability beyond acyclicity?
- Structural tractability of enumerating CSP solutions
- Hypertree width and related hypergraph invariants
- Graph-Theoretic Concepts in Computer Science
- Efficiently enumerating minimal triangulations
- Algorithms for propositional model counting
- Recognizing frozen variables in constraint satisfaction problems
- On sparse discretization for graphical games
- Regularizing conjunctive features for classification
- When is the evaluation of conjunctive queries tractable?
- Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons
- Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
- A unified theory of structural tractability for constraint satisfaction problems
- Algorithms for Propositional Model Counting
- Uniform Constraint Satisfaction Problems and Database Theory
- Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs
- Satisfiability of acyclic and almost acyclic CNF formulas
- Tractable counting of the answers to conjunctive queries
- Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Computing optimal hypertree decompositions with SAT
- Linear Programs with Conjunctive Database Queries
- Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
- Tree projections: Game characterization and computational aspects
- Answering conjunctive queries with inequalities
- D-FLAT: declarative problem solving using tree decompositions and answer-set programming
- Large hypertree width for sparse random hypergraphs
- Complexity Analysis of Generalized and Fractional Hypertree Decompositions
- Computing a partition function of a generalized pattern-based energy over a semiring
- Fast parallel hypertree decompositions in logarithmic recursion depth
- Balanced queries: divide and conquer
- Tree-Width for First Order Formulae
- Boolean tensor decomposition for conjunctive queries with negation
- Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
- Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
- Evaluating Datalog via tree automata and cycluits
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- Hyperconsistency width for constraint satisfaction: Algorithms and complexity results
- CSP beyond tractable constraint languages
- Schema mappings: a case of logical dynamics in database theory
- scientific article; zbMATH DE number 7561704 (Why is no real title available?)
This page was built for publication: Hypertree decompositions and tractable queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q696962)
