Tree projections and structural decomposition methods: minimality and game-theoretic characterization
From MaRDI portal
Publication:393903
DOI10.1016/j.tcs.2013.12.012zbMath1279.68277arXiv1212.2314OpenAlexW2016812993WikidataQ57782832 ScholiaQ57782832MaRDI QIDQ393903
Francesco Scarcello, Gianluigi Greco
Publication date: 24 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1212.2314
computational complexitytreewidthgames on hypergraphsgeneralized hypertree widthRobber and Captain gamestructural decomposition methods
Trees (05C05) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Games on graphs (graph-theoretic aspects) (05C57)
Related Items
The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
Cites Work
- Hypertree decompositions and tractable queries
- Graph minors. III. Planar tree-width
- A unified theory of structural tractability for constraint satisfaction problems
- Tree clustering for constraint networks
- Graph searching and a min-max theorem for tree-width
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- A comparison of structural CSP decomposition methods
- Structural tractability of enumerating CSP solutions
- Hypertree width and related hypergraph invariants
- Degrees of acyclicity for hypergraphs and relational database schemes
- Syntactic Characterization of Tree Database Schemas
- Marshals, monotone marshals, and hypertree-width
- Generalized hypertree decompositions: NP-hardness and tractable variants
- Tree Projections: Hypergraph Games and Minimality
- Connected Treewidth and Connected Graph Searching
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Constraint solving via fractional edge covers
- Power of Natural Semijoins
- Acyclic Hypergraph Projections
- Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
- On the Power of k-Consistency
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
