Geodesic
Satisfiability and computing van der Waerden numbers
The electronic journal of combinatorics, Tome 11 (2004) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In this paper we bring together the areas of combinatorics and propositional satisfiability. Many combinatorial theorems establish, often constructively, the existence of positive integer functions, without actually providing their closed algebraic form or tight lower and upper bounds. The area of Ramsey theory is especially rich in such results. Using the problem of computing van der Waerden numbers as an example, we show that these problems can be represented by parameterized propositional theories in such a way that decisions concerning their satisfiability determine the numbers (function) in question. We show that by using general-purpose complete and local-search techniques for testing propositional satisfiability, this approach becomes effective — competitive with specialized approaches. By following it, we were able to obtain several new results pertaining to the problem of computing van der Waerden numbers. We also note that due to their properties, especially their structural simplicity and computational hardness, propositional theories that arise in this research can be of use in development, testing and benchmarking of SAT solvers.
DOI : 10.37236/1794
Classification : 05D10, 03B35, 68Q25
Mots-clés : Ramsey theory, computing van der Waerden numbers, propositional satisfiability 
@article{10_37236_1794,
     author = {Michael R. Dransfield and Lengning Liu and Victor W. Marek and Miros{\l}aw Truszczy\'nski},
     title = {Satisfiability and computing van der {Waerden} numbers},
     journal = {The electronic journal of combinatorics},
     year = {2004},
     volume = {11},
     number = {1},
     doi = {10.37236/1794},
     zbl = {1054.05097},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1794/}
}
TY  - JOUR
AU  - Michael R. Dransfield
AU  - Lengning Liu
AU  - Victor W. Marek
AU  - Mirosław Truszczyński
TI  - Satisfiability and computing van der Waerden numbers
JO  - The electronic journal of combinatorics
PY  - 2004
VL  - 11
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1794/
DO  - 10.37236/1794
ID  - 10_37236_1794
ER  - 
%0 Journal Article
%A Michael R. Dransfield
%A Lengning Liu
%A Victor W. Marek
%A Mirosław Truszczyński
%T Satisfiability and computing van der Waerden numbers
%J The electronic journal of combinatorics
%D 2004
%V 11
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1794/
%R 10.37236/1794
%F 10_37236_1794
Michael R. Dransfield; Lengning Liu; Victor W. Marek; Mirosław Truszczyński. Satisfiability and computing van der Waerden numbers. The electronic journal of combinatorics, Tome 11 (2004) no. 1. doi: 10.37236/1794

Cité par Sources :