Tree projections: Game characterization and computational aspects

DOI10.1007/978-3-642-02029-2_21MaRDI QIDQ3655155zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Georg Gottlob, Gianluigi Greco, Zoltán Miklós, Francesco Scarcello, Thomas Schwentick

Publication date 7 January 2010

Published in Graph Theory, Computational Intelligence and Thought (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02029-2_21

zbMATH Keywords

computational complexityhypergraphstree projections

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Tree projections and structural decomposition methods: minimality and game-theoretic characterization
• Tree Projections: Hypergraph Games and Minimality
• scientific article; zbMATH DE number 1834638
• Acyclic Hypergraph Projections
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Acyclic Hypergraph Projections
• Complexity and algorithms for graph and hypergraph sandwich problems
• Connected Treewidth and Connected Graph Searching
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Graph minors. III. Planar tree-width
• Graph Sandwich Problems
• Graph searching and a min-max theorem for tree-width
• Hypertree decompositions and tractable queries
• Hypertree width and related hypergraph invariants
• Marshals, monotone marshals, and hypertree-width
• On the Power of k-Consistency
• Power of Natural Semijoins
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• Syntactic Characterization of Tree Database Schemas
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The tree projection theorem and relational query processing
• Tree Projections: Hypergraph Games and Minimality
• Tree-size bounded alternation

Cited in

(10)

• A note on first-order projections and games.
• Computing branching distances with quantitative games
• A game characterisation of tree-like Q-resolution size
• A Dynamic Algorithm for Reachability Games Played on Trees
• Tree Projections: Hypergraph Games and Minimality
• The Computational Complexity of Game Trees by Eigen-Distribution
• Thick Subtrees, Games and Experiments
• Tree projections and structural decomposition methods: minimality and game-theoretic characterization
• scientific article; zbMATH DE number 2080927 (Why is no real title available?)
• scientific article; zbMATH DE number 2086645 (Why is no real title available?)

This page was built for publication: Tree projections: Game characterization and computational aspects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3655155)