This article is cited in 1 paper

Polytopes and connected subgraphs

A. V. Seliverstov

Institute for Information Transmission Problems (Kharkevich Institute), RAS, 19 Bolshoy Karetny Lane, 127994 Moscow, Russia

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. 14.

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

UDC: 519.852.2

Received: 22.08.2013
Revised: 17.02.2014

Bibliographic databases:

•