KIAM Main page Web Library  •  Publication Searh  Русский 

Conference material: "Academician O.B. Lupanov XIV International Scientific Seminar "Discrete Mathematics and Its Applications" (20-25 June 2022, Moscow)"
Authors: Svistunova V.R.
Comparison of encodings and optimization of parameters of SAT-solver in graph coloring problem
The paper considers the problem of coloring graphs of a special type, reduction of this problem to the problem of satisfiability of Boolean formulas (SAT) and optimization of the parameters of the SAT solver, which allows solving problems of such view in less time. The problem of the existence of a proper coloring graph G in k colors is, generally speaking, NP-complete for k >= 3, and can be reduced in various ways to another well-known NP-complete problem - the problem of satisfiability of Boolean formulas in conjunctive normal form. The efficiency of the work can depend on the encoding SAT solvers (specialized programs for solving a problem feasibility). The parameters of the SAT solver Glucose were optimized using the genetic algorithm implemented in the PyDGGA package. Optimization made it possible to speed up Glucose by 3-5 times.
SAT-solvers, graph coloring
Publication language: russian,  pages: 3 (p. 198-200)
Russian source text:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Svistunova Victoria Romanovna,  Adyghe State University