Random 2-SAT with prescribed literal degrees

DOI10.1007/S00453-007-0082-7MaRDI QIDQ2642316zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Colin Cooper, Gregory B. Sorkin, Alan Frieze

Publication date 20 August 2007

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-0082-7

zbMATH Keywords

phase transitions

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2119678
• RANDOM 2‐SAT Does Not Depend on a Giant
• Rigorous results for random (2+p)-SAT
• Random 2-SAT and unsatisfiability
• Random 2-SAT: Results and problems

Cited in

(10)

• Popularity-similarity random SAT formulas
• RANDOM 2‐SAT Does Not Depend on a Giant
• scientific article; zbMATH DE number 2119678 (Why is no real title available?)
• Branching process approach for 2-SAT thresholds
• The satisfiability threshold for non-uniform random 2-SAT
• Satisfiability threshold for power law random 2-SAT in configuration model
• Random 2-SAT: Results and problems
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• The number of satisfying assignments of random 2‐SAT formulas
• Biased random k‐SAT

This page was built for publication: Random 2-SAT with prescribed literal degrees

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