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

DOI10.1111/itor.12194zbMath1348.90537arXiv1501.05407OpenAlexW2963253145MaRDI QIDQ2827757

Mathieu Dutour Sikirić, Michel Marie Deza

Publication date: 21 October 2016

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.05407

zbMATH Keywords

polyhedracombinatorial optimizationbranch and boundgraph theoryenumeration

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (7)

Generalized cut and metric polytopes of graphs and simplicial complexes ⋮ The bipartite Boolean quadric polytope ⋮ Retracts and algebraic properties of cut algebras ⋮ On the bond polytope ⋮ Moduli of polarised Enriques surfaces — Computational aspects ⋮ Seminormality, canonical modules, and regularity of cut polytopes ⋮ The hypermetric cone and polytope on eight vertices and some generalizations

Uses Software

• polymake

Cites Work

• The max-cut problem on graphs not contractible to \(K_ 5\)
• The contact polytope of the Leech lattice
• On the graph structure of convex polyhedra in \(n\)-space
• Matroids and multicommodity flows
• Computing extreme rays of the metric cone for seven points
• All the facets of the six-point Hamming cone
• All facets of the cut cone \(C_ n\) for \(n=7\) are known
• Computing convex hulls and counting integer points with \texttt{polymake}
• Computing symmetry groups of polyhedra
• Complexity and algorithms for computing Voronoi cells of lattices
• Classification of eight-dimensional perfect forms
• DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES
• On the cut polytope
• Leggett-Garg inequalities and the geometry of the cut polytope
• On the relationship between convex bodies related to correlation experiments with dichotomic observables
• Two-party Bell inequalities derived from combinatorics via triangular elimination

This page was built for publication: Enumeration of the facets of cut polytopes over some highly symmetric graphs