A sufficient condition for backtrack-bounded search
From MaRDI portal
Publication:3771663
DOI10.1145/4221.4225zbMATH Open0633.68096DBLPjournals/jacm/Freuder85OpenAlexW2080192364WikidataQ59595170 ScholiaQ59595170MaRDI QIDQ3771663FDOQ3771663
Publication date: 1985
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/4221.4225
constraint satisfactionrelaxationbiconnected componentbacktrack searchconstraint networksbacktrack treeconstraint consistency
Cited In (52)
- An algebraic characterization of tractable constraints
- Fugitive-search games on graphs and related parameters
- Hybrid Tractable Classes of Constraint Problems
- LP Formulations for Polynomial Optimization Problems
- Tradeoffs in the Complexity of Backdoor Detection
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- Uniform Constraint Satisfaction Problems and Database Theory
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Hypertree decompositions and tractable queries
- Tractable constraints on ordered domains
- Constraint satisfaction with bounded treewidth revisited
- Branch \& Sample: A simple strategy for constraint satisfaction
- A unified theory of structural tractability for constraint satisfaction problems
- A polynomial relational class of binary CSP
- Network-based heuristics for constraint-satisfaction problems
- Binary constraint satisfaction problems defined by excluded topological minors
- Constraints, consistency and closure
- Neighborhood singleton consistencies
- Characterising tractable constraints
- Decomposing constraint satisfaction problems using database techniques
- Counting representable sets on simple graphs
- Propositional semantics for disjunctive logic programs
- A comparison of structural CSP decomposition methods
- Weighted hypertree decompositions and optimal query plans
- A new tractable class of constraint satisfaction problems
- Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
- Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
- Galois connections for patterns: an algebra of labelled graphs
- Resource-constrained project scheduling: Notation, classification, models, and methods
- On the Minimal Constraint Satisfaction Problem: Complexity and Generation
- On computing minimal models
- Fugitive-search games on graphs and related parameters
- Computing and restoring global inverse consistency in interactive constraint satisfaction
- Accelerating filtering techniques for numeric CSPs
- Tractable constraints on ordered domains
- Domain filtering consistencies for non-binary constraints
- Local consistency for extended CSPs
- ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors
- Lower Bounds for Subgraph Detection in the CONGEST Model
- Model-based inference in CHARME.
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- New limits of treewidth-based tractability in optimization
- Representing and solving finite-domain constraint problems using systems of polynomials
- Disjunctions, independence, refinements
- Fast parallel constraint satisfaction
- Fast parallel constraint satisfaction
- Default reasoning using classical logic
- Algorithms and complexity results for persuasive argumentation
- On the power of structural decompositions of graph-based representations of constraint problems
- Decomposable constraints
- Dynamic algorithms for classes of constraint satisfaction problems
- Constraint reasoning
Recommendations
- An overview of backtrack search satisfiability algorithms 👍 👎
- Backjump-based backtracking for constraint satisfaction problems 👍 👎
- Bounded backtracking for the valued constraint satisfaction problems 👍 👎
- Title not available (Why is that?) 👍 👎
- Random backtracking in backtrack search algorithms for satisfiability 👍 👎
- Backtracking and random constraint satisfaction 👍 👎
- Hybrid backtracking bounded by tree-decomposition of constraint networks 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
This page was built for publication: A sufficient condition for backtrack-bounded search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3771663)
