Estimating satisfiability

DOI10.1016/J.DAM.2011.10.005zbMATH Open1252.90069OpenAlexW2912723616MaRDI QIDQ765341FDOQ765341

Thomas Hugel, Yacine Boufkhad

Publication date: 19 March 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.005

zbMATH Keywords

satisfiabilityconstraint satisfaction problemfirst moment method

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating the unsatisfiability threshold of random formulas
• Tail bounds for occupancy and the satisfiability threshold conjecture
• Random constraint satisfaction: A more accurate picture
• On the solution-space geometry of random constraint satisfaction problems
• On the satisfiability threshold of formulas with three literals per clause
• Pruning processes and a new characterization of convex geometries
• Almost all graphs with 2. 522\(n\) edges are not 3-colorable
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• A new look at survey propagation and its generalizations
• The unsatisfiability threshold revisited
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• Non Uniform Selection of Solutions for Upper Bounding the 3-SAT Threshold
• Regular random \(k\)-SAT: Properties of balanced formulas

Cited In (2)

• Solving satisfiability problems using elliptic approximations. A note on volumes and weights
• Satisfiability Judgement under Incomplete Information

This page was built for publication: Estimating satisfiability

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