On the convex hull of 3-cycles of the complete graph

On the convex hull of 3-cycles of the complete graph

0.00 Avg rating0 Votes
Article ID: iaor20084663
Country: Brazil
Volume: 23
Issue: 1
Start Page Number: 99
End Page Number: 109
Publication Date: Jan 2003
Journal: Pesquisa Operacional
Authors: , ,
Abstract:

Let Kn be the complete undirected graph with n vertices. A 3-cycle is a cycle consisting of 3 edges. The 3-cycle polytope is defined as the convex hull of the incidence vectors of all 3-cycles in Kn. In this paper, we present a polyhedral analysis of the 3-cycle polytope. In particular, we give several classes of facet defining inequalities of this polytope and we prove that the separation problem associated to one of these classes of inequalities is NP-complete. Finally, it is proved that the 3-cycle polytope is a 2-neighborly polytope.

Reviews

Required fields are marked *. Your email address will not be published.