Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
From MaRDI portal
Publication:1401972
Recommendations
Cites work
- 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
- 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?)
- 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
(40)- Hypertree-depth and minors in hypergraphs
- Evaluating Datalog via tree automata and cycluits
- Structural tractability of enumerating CSP solutions
- Hypertree width and related hypergraph invariants
- Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
- Marshals, monotone marshals, and hypertree-width
- Tree Projections: Hypergraph Games and Minimality
- Tree-Width for First Order Formulae
- Tree projections: Game characterization and computational aspects
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- The dag-width of directed graphs
- SOME MODEL THEORY OF GUARDED NEGATION
- Guarded Ontology-Mediated Queries
- The treewidth of 2-section of hypergraphs
- scientific article; zbMATH DE number 7104937 (Why is no real title available?)
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Uniform Constraint Satisfaction Problems and Database Theory
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- Computing optimal hypertree decompositions with SAT
- Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments
- Parameterized analysis of the cops and robber problem
- Going deep and going wide: counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
- Hunting a rabbit is hard
- Optimally rewriting formulas and database queries: a confluence of term rewriting, structural decomposition, and complexity
- FPT approximation of generalised hypertree width for bounded intersection hypergraphs
- Catching a robber on a random k-uniform hypergraph
- Further results on the hunters and rabbit game through monotonicity
- Hypertree decompositions and tractable queries
- Cop number of random k-uniform hypergraphs (extended abstract)
- On the complexity of entailment in existential conjunctive first-order logic with atomic negation
- Hunting a rabbit: complexity, approximability and some characterizations
- Optimally rewriting formulas and database queries: a confluence of term rewriting, structural decomposition, and complexity
- Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
- FPT approximation of generalised hypertree width for bounded intersection hypergraphs
- Going deep and going wide: counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
- Color refinement for relational structures
- 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
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)
