Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures

DOI10.1017/S0963548303005637zbMath1114.68429OpenAlexW2133747498MaRDI QIDQ4471151

Tomasz Jurdziński, Andreas Goerdt

Publication date: 18 June 2004

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548303005637

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65)

Related Items (2)

An efficient approach to solving random \(k\)-SAT problems ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT

This page was built for publication: Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures