A Sufficient Condition for Backtrack-Free Search
From MaRDI portal
Publication:3933756
DOI10.1145/322290.322292zbMath0477.68063OpenAlexW2002478775WikidataQ57259021 ScholiaQ57259021MaRDI QIDQ3933756
Publication date: 1982
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322290.322292
graph coloringconstraint satisfactioncombinatorial algorithmsbacktrackingconstraint network consistencyscene labeling
Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Information storage and retrieval of data (68P20)
Related Items
Fugitive-search games on graphs and related parameters, Projection, consistency, and George Boole, On point-duration networks for temporal reasoning, Experimental evaluation of preprocessing algorithms for constraint satisfaction problems, Fast parallel constraint satisfaction, Local consistency in parallel constraint satisfaction networks, An optimal backtrack algorithm for tree-structured constraint satisfaction problems, Model-based inference in CHARME., Binary constraint satisfaction problems defined by excluded topological minors, Iterative coloring extension of a maximum clique, Dense trees: a new look at degenerate graphs, A constraint-based approach to fast and exact structure prediction in three-dimensional protein models, The combinatorics of object recognition in cluttered environments using constrained search, Constraint relaxation may be perfect, Network-based heuristics for constraint-satisfaction problems, Variable ordering for decision diagrams: a portfolio approach, Decision-support with preference constraints, Theoretical analysis of singleton arc consistency and its extensions, Modelling and solving temporal reasoning as propositional satisfiability, Efficiently enumerating all maximal cliques with bit-parallelism, A review of literature on parallel constraint solving, Distributed CSPs by graph partitioning, Classes of linear programs solvable by coordinate-wise minimization, Tree clustering for constraint networks, Treewidth for graphs with small chordality, Branch \& Sample: A simple strategy for constraint satisfaction, On Singleton Arc Consistency for CSPs Defined by Monotone Patterns, No more ``Partial and ``Full Looking Ahead, Structure-driven algorithms for truth maintenance, From local to global consistency in temporal constraint networks, Local and global relational consistency, Fugitive-search games on graphs and related parameters, Networked bubble propagation: a polynomial-time hypothetical reasoning method for computing near-optimal solutions, Combining qualitative and quantitative constraints in temporal reasoning, On tree-preserving constraints, A probabilistic analysis of randomly generated binary constraint satisfaction problems., A non-binary constraint ordering heuristic for constraint satisfaction problems, Achieving consistency with cutting planes, A hybrid tractable class for non-binary CSPs, Unnamed Item, The power of propagation: when GAC is enough, On the monotonicity of games generated by symmetric submodular functions., Combining restarts, nogoods and bag-connected decompositions for solving csps, Tradeoffs in the Complexity of Backdoor Detection, Learning cluster-based structure to solve constraint satisfaction problems, A naive algorithm for feedback vertex set, Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search, How to survive while visiting a graph, Hybrid Tractable Classes of Constraint Problems, The complexity of reasoning with global constraints, Why Is Maximum Clique Often Easy in Practice?, Temporal constraint networks, Exact algorithms for maximum clique: a computational study, Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics, Model-based computing: Developing flexible machine control software, On singleton arc consistency for CSPs defined by monotone patterns, From local to global consistency, Integer programs for logic constraint satisfaction, Solving the minimum-weighted coloring problem, On some partial line graphs of a hypergraph and the associated matroid, A fuzzy constraint satisfaction approach for signal abstraction, Constraint reasoning based on interval arithmetic: The tolerance propagation approach, On exponential time lower bound of Knapsack under backtracking, SampleSearch: importance sampling in presence of determinism, Topological parameters for time-space tradeoff, Dynamic algorithms for classes of constraint satisfaction problems, Fusion, propagation, and structuring in belief networks, Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, Reasoning about cardinal directions between extended objects, Parameterized Complexity Results in Symmetry Breaking, Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning, Constructing an asymptotic phase transition in random binary constraint satisfaction problems, Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints, Approximated consistency for the automatic recording constraint, Resource-constrained project scheduling: Notation, classification, models, and methods, Constraints, consistency and closure, Degree Reduction in Labeled Graph Retrieval, Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems, Determining the consistency of partial tree descriptions, Salt: A knowledge acquisition language for propose-and-revise systems, On-line algorithms for networks of temporal constraints, A new branch-and-filter exact algorithm for binary constraint satisfaction problems, Backtracking algorithms for disjunctions of temporal constraints, On a new extension of BTP for binary CSPs, A new approach to cyclic ordering of 2D orientations using ternary relation algebras, A Logical Approach to Constraint Satisfaction, Decomposable constraints, Querying temporal and spatial constraint networks in PTIME, A comparison of structural CSP decomposition methods, Locally consistent constraint satisfaction problems, Fast parallel constraint satisfaction, Locally defined independence systems on graphs, Backjump-based backtracking for constraint satisfaction problems, Dynamic variable ordering in graph based backjumping algorithms for csps, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, Decomposing constraint satisfaction problems using database techniques, Characterising tractable constraints, Arc-consistency for continuous variables, Hybrid backtracking bounded by tree-decomposition of constraint networks, Fuzzy constraint networks for signal pattern recognition, A tabu search approach to the constraint satisfaction problem as a general problem solver
