scientific article; zbMATH DE number 1047722

MaRDI QIDQ4347889zbMATH OpenFDO

Authors Michel Deza, Viacheslav Grishukhin

Publication date 20 July 1998

zbMATH Keywords

cut conescut polyhedraHilbert basispolyhedral optimization

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Programming involving graphs or networks (90C35)

Review text

Let \(K_n=(V_n,E_n)\) denote the complete graph with \(n\) vertices, and for \(S \subset V_n\) denote by \(\delta(S)\) the subset of edges \(\{i,j\}\) with the property \(S \cap \{i,j\}\) is a single vertex. The sets are called `em-cuts'. The incidence vectors of cuts are called cut vectors. This paper studies the cone \(R_+(K_n)\) in \(R^n\) generated by cut vectors as well as the lattice \(Z(K_n)\) and the cone \(Z_+(K_n)\). The main discussion regards the set of points \(A_n^i\) of those points in \(R_+(K_n) \cap Z(K_n)\) with \(i\) representations in \(Z_+(K_n)\). For the entire collection see [Zbl 0865.00038].

Recommendations

• Lattice Points of Cut Cones
• scientific article; zbMATH DE number 427739
• Delaunay polytopes of cut lattices

Cited in

(6)

• Extension operations for cuts
• Hilbert bases of cuts
• The concept of cutting vectors for vector systems in the Euclidean plane
• scientific article; zbMATH DE number 427739 (Why is no real title available?)
• Lattice Points of Cut Cones
• The Hilbert basis of the cut cone over the complete graph \(K_6\)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4347889)