scientific article; zbMATH DE number 1448978
From MaRDI portal
Publication:4954175
zbMath0940.68099MaRDI QIDQ4954175
Publication date: 18 May 2000
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (46)
Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden ⋮ A sharp threshold for a random constraint satisfaction problem ⋮ Many hard examples in exact phase transitions ⋮ Nature-inspired techniques for dynamic constraint satisfaction problems ⋮ Lower and Upper Bounds for Random Mimimum Satisfiability Problem ⋮ Super Solutions of Random Instances of Satisfiability ⋮ Statistical regimes across constrainedness regions ⋮ Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ The solution space structure of planted constraint satisfaction problems with growing domains ⋮ Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ Combinatorial sharpness criterion and phase transition classification for random CSPs ⋮ The scaling window of the model \(d\)-\(k\)-CSP ⋮ An upper (lower) bound for Max (Min) CSP ⋮ A tighter upper bound for random MAX \(2\)-SAT ⋮ Threshold behaviors of a random constraint satisfaction problem with exact phase transitions ⋮ Complete Boolean satisfiability solving algorithms based on local search ⋮ Dealing with satisfiability and \(n\)-ary CSPs in a logical framework ⋮ Local search with edge weighting and configuration checking heuristics for minimum vertex cover ⋮ On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. ⋮ Incremental Upper Bound for the Maximum Clique Problem ⋮ A Model to Study Phase Transition and Plateaus in Relational Learning ⋮ Phase transitions of contingent planning problem ⋮ Fractional Edge Cover Number of Model RB ⋮ Empirical Study of Phase Transition of Hamiltonian Cycle Problem in Random Graphs with Degrees Greater Than One ⋮ Phase Transition for Maximum Not-All-Equal Satisfiability ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability ⋮ A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming ⋮ On the phase transitions of \((k, q)\)-SAT ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ On the Minimal Constraint Satisfaction Problem: Complexity and Generation ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ Constructing an asymptotic phase transition in random binary constraint satisfaction problems ⋮ Bounding the scaling window of random constraint satisfaction problems ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ The SAT-UNSAT transition for random constraint satisfaction problems ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ A new branch-and-filter exact algorithm for binary constraint satisfaction problems ⋮ Reasoning from last conflict(s) in constraint programming ⋮ On the hardness of solving edge matching puzzles as SAT or CSP problems ⋮ Large hypertree width for sparse random hypergraphs ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length ⋮ On the constraint length of random \(k\)-CSP
This page was built for publication:
