scientific article

Peter C. Cheeseman, Bob Kanefsky, William M. Taylor

Publication date: 27 September 1992

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (only showing first 100 items - show all)

A Model for Phase Transition of Random Answer-Set Programs ⋮ GD-SAT model and crossover line ⋮ Critical Density Thresholds in Distributed Wireless Networks ⋮ Disordered systems insights on computational hardness ⋮ The phase transition in random horn satisfiability and its algorithmic implications ⋮ On the Integration of Singleton Consistencies and Look-Ahead Heuristics ⋮ The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘) ⋮ Complexity of Coloring Random Graphs ⋮ Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems ⋮ Problem structure heuristics and scaling behavior for genetic algorithms ⋮ Generating Difficult CNF Instances in Unexplored Constrainedness Regions ⋮ The number of satisfying assignments of random 2‐SAT formulas ⋮ Random Instances of W[2-Complete Problems: Thresholds, Complexity, and Algorithms] ⋮ Random logic programs: Linear model ⋮ Introduction to the dynamics of disordered systems: equilibrium and gradient descent ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ Hierarchical Hardness Models for SAT ⋮ What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO ⋮ Fractional Edge Cover Number of Model RB ⋮ Empirical Study of Phase Transition of Hamiltonian Cycle Problem in Random Graphs with Degrees Greater Than One ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses ⋮ Iterative state-space reduction for flexible computation ⋮ An Upper Bound on the Space Complexity of Random Formulae in Resolution ⋮ Quantum optimization ⋮ Complexity studies of a temporal constraint propagation algorithm: a statistical analysis ⋮ A physicist's approach to number partitioning ⋮ Frozen development in graph coloring ⋮ Constructing an asymptotic phase transition in random binary constraint satisfaction problems ⋮ Performance of linear-space search algorithms ⋮ Performance of linear-space search algorithms ⋮ Constraint Satisfaction ⋮ Edge-Matching Problems with Rotations ⋮ Turing Machines with Shortcuts: Efficient Attribute-Based Encryption for Bounded Functions ⋮ Optimization-Based Very Large-Scale Neighborhood Search for Generalized Assignment Problems with Location/Allocation Considerations ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Parameterized Complexity ⋮ SAT Distributions with Phase Transitions between Decision and Optimization Problems ⋮ Walksat Stalls Well Below Satisfiability ⋮ Generic properties of a computational task predict human effort and performance ⋮ The computational complexity of propositional STRIPS planning ⋮ The hardest constraint problems: A double phase transition ⋮ Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study ⋮ Downward refinement and the efficiency of hierarchical problem solving ⋮ Exploiting the deep structure of constraint problems ⋮ Easy problems are sometimes hard ⋮ Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ A new class of hard problem instances for the 0-1 knapsack problem ⋮ Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm ⋮ Completeness, approximability and exponential time results for counting problems with easy decision version ⋮ Regular-SAT: A many-valued approach to solving combinatorial problems ⋮ Modelling and solving temporal reasoning as propositional satisfiability ⋮ On Monte Carlo tree search for weighted vertex coloring ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ Planning as satisfiability: heuristics ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ Regular pattern-free coloring ⋮ Some computational aspects of DISTANCE SAT ⋮ A systematic study on meta-heuristic approaches for solving the graph coloring problem ⋮ Resolving Braess's paradox in random networks ⋮ Testing heuristics: We have it all wrong ⋮ Cardinal: a finite sets constraint solver ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Phase transitions and the search problem ⋮ Generating hard satisfiability problems ⋮ Experimental results on the crossover point in random 3-SAT ⋮ The satisfiability constraint gap ⋮ An empirical study of phase transitions in binary constraint satisfaction problems ⋮ Some pitfalls for experimenters with random SAT ⋮ Refining the phase transition in combinatorial search ⋮ Locating the phase transition in binary constraint satisfaction problems ⋮ A study of complexity transitions on the asymmetric traveling salesman problem ⋮ A probabilistic analysis of propositional STRIPS planning ⋮ Critical behavior in the computational cost of satisfiability testing ⋮ The TSP phase transition ⋮ Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Exploring the role of graph spectra in graph coloring algorithm performance ⋮ An upper (lower) bound for Max (Min) CSP ⋮ Discovering the suitability of optimisation algorithms by learning from evolved instances ⋮ Generalized probabilistic satisfiability and applications to modelling attackers with side-channel capabilities ⋮ Processing disjunctions in temporal constraint networks ⋮ The asymptotic \(k\)-SAT threshold ⋮ Algorithms and mechanisms for procuring services with uncertain durations using redundancy ⋮ SAT problems with chains of dependent variables ⋮ Probabilistic satisfiability: algorithms with the presence and absence of a phase transition ⋮ On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. ⋮ Manipulation can be hard in tractable voting systems even for constant-sized coalitions ⋮ Modelling the dynamics of stochastic local search on \(k\)-SAT ⋮ Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering ⋮ Asynchronous aggregation and consistency in distributed constraint satisfaction ⋮ Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks ⋮ Algorithm runtime prediction: methods \& evaluation ⋮ Exact algorithms for maximum clique: a computational study ⋮ Multi-threading a state-of-the-art maximum clique algorithm ⋮ Visualizing SAT instances and runs of the DPLL algorithm ⋮ Constraint satisfaction -- algorithms and complexity analysis ⋮ Review on nature-inspired algorithms

This page was built for publication: