A probabilistic analysis of randomly generated binary constraint satisfaction problems.

DOI10.1016/S0304-3975(02)00317-1MaRDI QIDQ1401196zbMATH OpenOpenAlexDBLPWikidataFDO

Authors D. Massart

Publication date 17 August 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(02)00317-1

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Theory and Applications of Satisfiability Testing
• GA performance distributions and randomly generated binary constraint satisfaction problems.
• A general model and thresholds for random constraint satisfaction problems
• A probabilistic study on the satisfiability problem
• Probabilistic analysis of satisfiability algorithms
• Models for Random Constraint Satisfaction Problems
• scientific article; zbMATH DE number 1002207
• scientific article; zbMATH DE number 1947423

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A Sufficient Condition for Backtrack-Free Search
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Sudden emergence of a giant k-core in a random graph
• The asymptotic number of labeled graphs with given degree sequences

Cited in

(9)

• Decision network semantics of branching constraint satisfaction problems
• Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem
• Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
• The scaling window of the model \(d\)-\(k\)-CSP
• A general model and thresholds for random constraint satisfaction problems
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• An average analysis of backtracking on random constraint satisfaction problems
• A new branch-and-filter exact algorithm for binary constraint satisfaction problems
• Many hard examples in exact phase transitions

This page was built for publication: A probabilistic analysis of randomly generated binary constraint satisfaction problems.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401196)