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

DOI10.1016/S0022-0000(03)00030-8zbMath1054.68044WikidataQ59259702 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)

Mathematics Subject Classification ID

68P15: Database theory

91A43: Games involving graphs

68R10: Graph theory (including graph drawing) in computer science

03B70: Logic in computer science

05C75: Structural characterization of families of graphs

Related Items

Uniform Constraint Satisfaction Problems and Database Theory, Hypertree decompositions and tractable queries, Weighted hypertree decompositions and optimal query plans, An annotated bibliography on guaranteed graph searching, A unified theory of structural tractability for constraint satisfaction problems, CSP duality and trees of bounded pathwidth, Hypertree width and related hypergraph invariants, Tree-Width for First Order Formulae, Tree Projections: Game Characterization and Computational Aspects

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