Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
DOI10.1016/S0022-0000(03)00030-8zbMATH Open1054.68044OpenAlexW2628596753WikidataQ59259702 ScholiaQ59259702MaRDI QIDQ1401972FDOQ1401972
Authors: Georg Gottlob, N. 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
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Database theory (68P15) Games involving graphs (91A43) Logic in computer science (03B70)
Cites Work
- Datalog LITE
- Graph searching and a min-max theorem for tree-width
- Title not available (Why is that?)
- Handle-rewriting hypergraph grammars
- Decomposing constraint satisfaction problems using database techniques
- A comparison of structural CSP decomposition methods
- Conjunctive-query containment and constraint satisfaction
- Graph minors. II. Algorithmic aspects of tree-width
- When is the evaluation of conjunctive queries tractable?
- Hypertree decompositions and tractable queries
- The complexity of acyclic conjunctive queries
- Tree clustering for constraint networks
- A sufficient condition for backtrack-bounded search
- Acyclic Hypergraph Projections
- Information integration using logical views
- On the Restraining Power of Guards
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computing LOGCFL certificates
Cited In (27)
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- The dag-width of directed graphs
- Tree-Width for First Order Formulae
- Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments
- Uniform Constraint Satisfaction Problems and Database Theory
- An annotated bibliography on guaranteed graph searching
- Hypertree decompositions and tractable queries
- On the complexity of entailment in existential conjunctive first-order logic with atomic negation
- A unified theory of structural tractability for constraint satisfaction problems
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- Title not available (Why is that?)
- Weighted hypertree decompositions and optimal query plans
- SOME MODEL THEORY OF GUARDED NEGATION
- Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
- The treewidth of 2-section of hypergraphs
- Hypertree-depth and minors in hypergraphs
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Structural tractability of enumerating CSP solutions
- Marshals, monotone marshals, and hypertree-width
- Hypertree width and related hypergraph invariants
- Guarded Ontology-Mediated Queries
- Tree Projections: Hypergraph Games and Minimality
- Evaluating Datalog via tree automata and cycluits
- CSP duality and trees of bounded pathwidth
- Tree projections: Game characterization and computational aspects
- Computing optimal hypertree decompositions with SAT
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
This page was built for publication: Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401972)
