Output details
11 - Computer Science and Informatics
Middlesex University
Return to search
Output 0 of 0 in the submission
Output title
Combinatorial landscape analysis for k-SAT instances
Type
E - Conference contribution
Name of conference/published proceedings
IEEE Congress on Evolutionary Computation
Volume number
-
Issue number
-
First page of article
2498
ISSN of proceedings
-
Year of publication
2008
URL
-
Number of additional authors
2
Additional information
<13>While there are rigorous methods for establishing the asymptotic behaviour of the k-SAT phase transition threshold from satisfiable CNFs to unsatisfiable CNFs, there is still the problem of deciding satisfiability for each individual CNF. The paper presents the very first method of approximating the number of local maxima - fitness function equals the number of satisfied clauses -, which then can be used to identify the set of local maxima. Among the local maxima one can then search for global maxima where all clauses are satisfied. The approach has been later successfully applied to RNA folding landscapes, published in Bioinformatics.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
2
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
