scientific article; zbMATH DE number 1754601
From MaRDI portal
zbMath0986.68042MaRDI QIDQ4535026
Publication date: 12 June 2002
Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2076/20760310
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT, Exact and approximative algorithms for coloring G(n,p), The resolution complexity of random graph \(k\)-colorability, Resolution complexity of random constraint satisfaction problems: Another half of the story, Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story, Recognizing more random unsatisfiable 3-SAT instances efficiently
