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 K-8, K-3,K-3,K-3, K-1,K-4,K-4, K-5,K-5, some other K-l,K-m, K-1,K-l,K-m, Prism(7), APrism(6), Mobius ladder M-14, dodecahedron, Heawood, and Petersen graphs. For K-8, 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 K-1,K-l,K-m with (l, m) = (4, 4), (3, 5), (3, 4) solve problems in the quantum information theory. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1111/itor.12194 | INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH |
Keywords | Field | DocType |
enumeration, graph theory, polyhedra, branch and bound, combinatorial optimization | Discrete mathematics,Graph,Combinatorics,Enumeration,Polytope,Facet (geometry),Quantum information,Conjecture,Mathematics,Dodecahedron,Computation | Journal |
Volume | Issue | ISSN |
23 | 5 | 0969-6016 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michel Deza | 1 | 281 | 68.20 |
Mathieu Dutour Sikiric | 2 | 18 | 4.50 |