On nonintegral vertices of 3-SAT problem relaxation polytope

Modelirovanie i Analiz Informacionnyh Sistem. 2010;17(2):99-111


Journal Homepage

Journal Title: Modelirovanie i Analiz Informacionnyh Sistem

ISSN: 1818-1015 (Print); 2313-5417 (Online)

Publisher: Yaroslavl State University

Society/Institution: P.G. Demidov Yaroslavl State University

LCC Subject Category: Technology: Technology (General): Industrial engineering. Management engineering: Information technology

Country of publisher: Russian Federation

Language of fulltext: Russian, English

Full-text formats available: PDF



A. V. Nikolaev (Ярославский государственный университет им. П.Г. Демидова)


Double blind peer review

Editorial Board

Instructions for authors

Time From Submission to Publication: 8 weeks


Abstract | Full Text

New facts characterizing the vertex set of 3-SAT problem relaxation polytope are established. In particular, the question of preservation of nonintegral vertices under additional linear constraints of stronger relaxations is examined.