Enumeration of the facets of cut polytopes over some highly symmetric graphs

Enumeration of the facets of cut polytopes over some highly symmetric graphs

0.00 Avg rating0 Votes
Article ID: iaor20162121
Volume: 23
Issue: 5
Start Page Number: 853
End Page Number: 860
Publication Date: Sep 2016
Journal: International Transactions in Operational Research
Authors: ,
Keywords: cutting plane algorithms, graphical methods
Abstract:

We report here a computation giving the complete list of facets for the cut polytopes over several very symmetric graphs with 15–30 edges, including K8, K3, 3, 3, K1, 4, 4, K5, 5, some other Kl,m, K1,l,m, Prism7,APrism6, Möbius ladder M14, dodecahedron, Heawood, and Petersen graphs. For K8, it shows that the huge list of facets of the cut polytope CUTP8 and cut cone CUT8, given in the literature is complete. We also confirm the conjecture that any facet of CUTP8 is adjacent to a triangle facet. The lists of facets for K1,l,m with (l,m)=(4,4),(3,5),(3,4) solve problems in the quantum information theory.

Reviews

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