Volume 21, No 3, 2014, P. 82-86

UDC 519.852.2
A. V. Seliverstov
Polytopes and connected subgraphs

Abstract:
The edges of the linear relaxation polytopes for quadratic Boolean programming problems are described. We found correspondence between the edges of such a polytope and connected subgraphs of the complete graph.
Tab. 1, bibliogr. 12.

Keywords: combinatorial optimization, polyhedral cone, polytope, subgraph.

Seliverstov Alexandr Vladislavovich ¹
1. Institute for Information Transmission Problems (Kharkevich Institute), RAS,
19 Bolshoy Karetny Lane, 127994 Moscow, Russia
e-mail: slvstv@iitp.ru