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

DOI10.1016/S0022-0000(03)00030-8MaRDI QIDQ1401972zbMATH OpenOpenAlexWikidataFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• Marshals, monotone marshals, and hypertree-width
• Hypertree decompositions and tractable queries
• Hypertree-width and related hypergraph invariants
• Hypertree width and related hypergraph invariants
• Tree-Related Widths of Graphs and Hypergraphs

Cites work

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

Cited in

(27)

• Tree projections and structural decomposition methods: minimality and game-theoretic characterization
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• 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
• An annotated bibliography on guaranteed graph searching
• Uniform Constraint Satisfaction Problems and Database Theory
• 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
• Weighted hypertree decompositions and optimal query plans
• scientific article; zbMATH DE number 7104937 (Why is no real title available?)
• SOME MODEL THEORY OF GUARDED NEGATION
• Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
• Hypertree-depth and minors in hypergraphs
• The treewidth of 2-section of 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
• Tree Projections: Hypergraph Games and Minimality
• Guarded Ontology-Mediated Queries
• 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

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)