𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Better Algorithm for Random k -SAT

✍ Scribed by Coja-Oghlan, Amin

Book ID
118181092
Publisher
Society for Industrial and Applied Mathematics
Year
2010
Tongue
English
Weight
499 KB
Volume
39
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A Randomized Algorithm for 3-SAT
A Randomized Algorithm for 3-SAT
✍ Subhas Kumar Ghosh; Janardan Misra πŸ“‚ Article πŸ“… 2010 πŸ› Springer-Verlag 🌐 English βš– 257 KB
Randomized Algorithms for 3-SAT
Randomized Algorithms for 3-SAT
✍ Thomas Hofmeister; Uwe Schoning; Rainer Schuler; Osamu Watanabe πŸ“‚ Article πŸ“… 2006 πŸ› Springer 🌐 English βš– 228 KB
An improved exponential-time algorithm f
An improved exponential-time algorithm for k -SAT
✍ Paturi, Ramamohan; PudlΓ‘k, Pavel; Saks, Michael E.; Zane, Francis πŸ“‚ Article πŸ“… 2005 πŸ› Association for Computing Machinery 🌐 English βš– 222 KB
A randomized algorithm for k-colorabilit
A randomized algorithm for k-colorability
✍ Janez Ε½erovnik πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 692 KB

This note is a report of testing a straightforward generalization of the randomized 3-coloring algorithm of Petford and Welsh (1989) on the decision problems of 4-and lo-coloring. We observe similar behavior, namely the existence of critical regions. Experimentally, the average time complexity for