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

Andreas Goerdt Tomasz Jurdzinski

Published in: MFCS (2002)

Keyphrases

approximation algorithms
special case
np hard
randomly generated
sat instances
worst case
phase transition
sat solvers
randomized algorithms
linear programming
satisfiability problem
disjoint paths
genetic algorithm
knowledge representation