Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.

DOI10.1016/S0022-0000(03)00030-8zbMath1054.68044OpenAlexW2628596753WikidataQ59259702 ScholiaQ59259702MaRDI QIDQ1401972

Georg Gottlob, Nicola Leone, Francesco Scarcello

Publication date: 19 August 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(03)00030-8

Mathematics Subject Classification ID

Database theory (68P15) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Logic in computer science (03B70) Structural characterization of families of graphs (05C75)

Related Items (25)

The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ Weighted hypertree decompositions and optimal query plans ⋮ Hypertree-depth and minors in hypergraphs ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ Computing optimal hypertree decompositions with SAT ⋮ Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments ⋮ The dag-width of directed graphs ⋮ An annotated bibliography on guaranteed graph searching ⋮ A unified theory of structural tractability for constraint satisfaction problems ⋮ Hypertree width and related hypergraph invariants ⋮ SOME MODEL THEORY OF GUARDED NEGATION ⋮ Hypertree decompositions and tractable queries ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ On the complexity of entailment in existential conjunctive first-order logic with atomic negation ⋮ CSP duality and trees of bounded pathwidth ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints ⋮ Tree-Width for First Order Formulae ⋮ Evaluating Datalog via tree automata and cycluits ⋮ Tree Projections: Game Characterization and Computational Aspects ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Structural tractability of enumerating CSP solutions ⋮ Guarded Ontology-Mediated Queries ⋮ The treewidth of 2-section of hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypertree decompositions and tractable queries
• Tree clustering for constraint networks
• Decomposing constraint satisfaction problems using database techniques
• Graph searching and a min-max theorem for tree-width
• Information integration using logical views
• A comparison of structural CSP decomposition methods
• Conjunctive-query containment and constraint satisfaction
• Handle-rewriting hypergraph grammars
• The complexity of acyclic conjunctive queries
• Graph minors. II. Algorithmic aspects of tree-width
• A sufficient condition for backtrack-bounded search
• Acyclic Hypergraph Projections
• On the Restraining Power of Guards
• When is the evaluation of conjunctive queries tractable?
• Datalog LITE
• Computing LOGCFL certificates

This page was built for publication: Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.