A sufficient condition for backtrack-bounded search
From MaRDI portal
Publication:3771663
DOI10.1145/4221.4225zbMath0633.68096OpenAlexW2080192364WikidataQ59595170 ScholiaQ59595170MaRDI QIDQ3771663
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
relaxationbacktrack searchconstraint networksconstraint satisfactionbiconnected componentbacktrack treeconstraint consistency
Related Items
Disjunctions, independence, refinements, Fast parallel constraint satisfaction, Model-based inference in CHARME., Binary constraint satisfaction problems defined by excluded topological minors, Constraint satisfaction with bounded treewidth revisited, Network-based heuristics for constraint-satisfaction problems, Computing and restoring global inverse consistency in interactive constraint satisfaction, Domain filtering consistencies for non-binary constraints, Representing and solving finite-domain constraint problems using systems of polynomials, Default reasoning using classical logic, Branch \& Sample: A simple strategy for constraint satisfaction, On computing minimal models, Lower Bounds for Subgraph Detection in the CONGEST Model, Weighted hypertree decompositions and optimal query plans, Propositional semantics for disjunctive logic programs, Fugitive-search games on graphs and related parameters, An algebraic characterization of tractable constraints, Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width., Tradeoffs in the Complexity of Backdoor Detection, Algorithms and complexity results for persuasive argumentation, Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search, Hybrid Tractable Classes of Constraint Problems, A unified theory of structural tractability for constraint satisfaction problems, LP Formulations for Polynomial Optimization Problems, Fugitive-search games on graphs and related parameters, Hypertree decompositions and tractable queries, On the power of structural decompositions of graph-based representations of constraint problems, On the Minimal Constraint Satisfaction Problem: Complexity and Generation, Dynamic algorithms for classes of constraint satisfaction problems, A new tractable class of constraint satisfaction problems, A polynomial relational class of binary CSP, Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors, Tractable constraints on ordered domains, Tractable constraints on ordered domains, 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, Constraints, consistency and closure, Local consistency for extended CSPs, Neighborhood singleton consistencies, Uniform Constraint Satisfaction Problems and Database Theory, Decomposable constraints, A comparison of structural CSP decomposition methods, Fast parallel constraint satisfaction, Counting representable sets on simple graphs, Fixed-parameter complexity in AI and nonmonotonic reasoning, Accelerating filtering techniques for numeric CSPs, Decomposing constraint satisfaction problems using database techniques, Characterising tractable constraints, New limits of treewidth-based tractability in optimization
