Delaying satisfiability for random 2SAT

DOI10.1002/RSA.20465zbMath1272.05185OpenAlexW2096307009MaRDI QIDQ2852549

Dan Vilenchik, Alistair Sinclair

Publication date: 9 October 2013

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20465

zbMATH Keywords

Achlioptas processrandom structuresrandom SATthreshold phenomenon

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Waiter-client and client-waiter colourability and \(k\)-SAT games ⋮ Random k -SAT and the power of two choices ⋮ On the Power of Choice for Boolean Functions

Cites Work

• A threshold for unsatisfiability
• Birth control for giants
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• Avoiding a giant component
• Hamiltonicity thresholds in Achlioptas processes
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• RANDOM 2‐SAT Does Not Depend on a Giant
• Avoiding small subgraphs in Achlioptas processes
• Sharp thresholds of graph properties, and the $k$-sat problem
• Balanced Allocations
• Creating a Giant Component
• A phase transition for avoiding a giant component
• Embracing the giant component

This page was built for publication: Delaying satisfiability for random 2SAT