Tree clustering for constraint networks
From MaRDI portal
The paper offers a systematic way of regrouping constraints into hierarchical structures capable of supporting seach without backtracking. The method involves the formation and preprocessing of an acyclic database that permits a large variety of queries and local perturbations to be processed swiftly, either by sequential backtrack-free procedures, or by distributed constraint propagation processes.
Recommendations
Cites work
- A Sufficient Condition for Backtrack-Free Search
- Complexity of Finding Embeddings in a k-Tree
- scientific article; zbMATH DE number 3823168 (Why is no real title available?)
- scientific article; zbMATH DE number 4081531 (Why is no real title available?)
- scientific article; zbMATH DE number 4112072 (Why is no real title available?)
- scientific article; zbMATH DE number 4121482 (Why is no real title available?)
- Network-based heuristics for constraint-satisfaction problems
- Networks of constraints: Fundamental properties and applications to picture processing
- Nonserial dynamic programming
- On the Desirability of Acyclic Database Schemes
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Synthesizing constraint expressions
Cited in
(93)- AND/OR search spaces for graphical models
- Temporal constraint networks
- From local to global consistency
- Integer programs for logic constraint satisfaction
- Constraint reasoning based on interval arithmetic: The tolerance propagation approach
- Structure identification in relational data
- Decomposing constraint satisfaction problems using database techniques
- Experimental evaluation of preprocessing algorithms for constraint satisfaction problems
- Accelerating new product development by overcoming complexity constraints
- On computing minimal models
- Local and global relational consistency
- Fugitive-search games on graphs and related parameters
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Decomposable constraints
- A comparison of structural CSP decomposition methods
- Conjunctive-query containment and constraint satisfaction
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Backjump-based backtracking for constraint satisfaction problems
- Compiling constraint satisfaction problems
- Binary vs. non-binary constraints
- On point-duration networks for temporal reasoning
- Binary constraint satisfaction problems defined by excluded topological minors
- The power of propagation: when GAC is enough
- Combining restarts, nogoods and bag-connected decompositions for solving csps
- Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
- Clustering for Petri nets
- Focusing on independent diagnosis problems
- Propositional semantics for disjunctive logic programs
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- Constraint satisfaction with succinctly specified relations
- Finding and counting permutations via CSPs
- Galois connections for patterns: an algebra of labelled graphs
- Optimization of a recursive conveyor by reduction to a constraint satisfaction problem
- A new branch-and-filter exact algorithm for binary constraint satisfaction problems
- New limits of treewidth-based tractability in optimization
- Default reasoning using classical logic
- On a new extension of BTP for binary CSPs
- STR3: a path-optimal filtering algorithm for table constraints
- Structural tractability of enumerating CSP solutions
- Large hypertree width for sparse random hypergraphs
- Domain permutation reduction for constraint satisfaction problems
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- Bounded-width QBF is PSPACE-complete
- The complexity of reasoning with global constraints
- Unifying tree decompositions for reasoning in graphical models
- Partition-based logical reasoning for first-order and propositional theories
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Structure-driven algorithms for truth maintenance
- The complexity of constraint satisfaction revisited
- Uncovering trees in constraint networks
- Combining qualitative and quantitative constraints in temporal reasoning
- Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
- Exploiting separators for guiding VNS
- Parameterized complexity results in symmetry breaking
- Computational social choice for coordination in agent networks
- Dynamic Management of Heuristics for Solving Structured CSPs
- Tree projections and structural decomposition methods: minimality and game-theoretic characterization
- scientific article; zbMATH DE number 67813 (Why is no real title available?)
- STR2: optimized simple tabular reduction for table constraints
- Using artificial neural networks for constraint satisfaction problem
- Constraint Satisfaction
- Dynamic variable ordering in graph based backjumping algorithms for csps
- Guarantees and limits of preprocessing in constraint satisfaction and reasoning
- LP formulations for polynomial optimization problems
- A review of tree convex sets test
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Binarisation for valued constraint satisfaction problems
- A Logical Approach to Constraint Satisfaction
- A sufficiently fast algorithm for finding close to optimal clique trees
- Topological parameters for time-space tradeoff
- Recursive conditioning
- Diagnosing tree-structured systems
- Consistency restoration and explanations in dynamic CSPs---Application to configuration
- Computing a partition function of a generalized pattern-based energy over a semiring
- Fugitive-search games on graphs and related parameters
- Learning cluster-based structure to solve constraint satisfaction problems
- Constraint reasoning
- Hypertree decompositions and tractable queries
- Complexity framework for forbidden subgraphs. I: The framework
- Graph homomorphism, monotone classes and bounded pathwidth
- Complexity framework for forbidden subgraphs. II: Edge subdivision and the ``H-graphs
- Counting permutation patterns with multidimensional trees
- Hybrid backtracking bounded by tree-decomposition of constraint networks
- Compiling propositional weighted bases
- Constraint satisfaction with bounded treewidth revisited
- Approximation algorithms for treewidth
- Reformulation of global constraints based on constraints checkers
- Constraint models for the covering test problem
- Coalition structure generation: a survey
- A unified theory of structural tractability for constraint satisfaction problems
- The expressive power of valued constraints: Hierarchies and collapses
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
This page was built for publication: Tree clustering for constraint networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116363)
