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

UDC 519.852.2
A. V. Seliverstov
Polytopes and connected subgraphs

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
1. Institute for Information Transmission Problems (Kharkevich Institute), RAS,
19 Bolshoy Karetny Lane, 127994 Moscow, Russia
e-mail: slvstv@iitp.ru

 © Sobolev Institute of Mathematics, 2015