Structural decompositions for problems with global constraints

DOI10.1007/s10601-015-9181-2zbMath1334.90192arXiv1502.02467MaRDI QIDQ272005

Evgenij Thorstensen

Publication date: 20 April 2016

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.02467

zbMATH Keywords

tractability; global constraints; structural restrictions

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

Uses Software

• MINION

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypertree decompositions and tractable queries
• A unified theory of structural tractability for constraint satisfaction problems
• Simultaneous matchings: Hardness and approximation
• A comparison of structural CSP decomposition methods
• Constraint satisfaction with succinctly specified relations
• Tractable cases of the extended global cardinality constraint
• The complexity of reasoning with global constraints
• Hypertree width and related hypergraph invariants
• Parametrized complexity theory.
• Size Bounds and Query Plans for Relational Joins
• Backdoors to Satisfaction
• Approximating fractional hypertree width
• Optimization Methods for the Partner Units Problem
• Typed Guarded Decompositions for Constraint Satisfaction
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Constraint solving via fractional edge covers
• Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
• Principles and Practice of Constraint Programming – CP 2004