The cut cone. III: On the role of triangle facets

DOI10.1007/BF02350631zbMath0777.90047OpenAlexW4240790620MaRDI QIDQ5905548

Michel Marie Deza, Svatopluk Poljak, Monique Laurent

Publication date: 16 January 1993

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02350631

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27)

Related Items

Application of cut polyhedra. I, The expected relative error of the polyhedral approximation of the max- cut problem, On a positive semidefinite relaxation of the cut polytope, Lattice Points of Cut Cones, One-third-integrality in the max-cut problem, The even and odd cut polytopes, \(k\)-neighborly faces of the Boolean quadric polytopes, Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes

Cites Work

• The even and odd cut polytopes
• On qualitatively independent partitions and related problems
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Computing extreme rays of the metric cone for seven points
• Facets for the cut cone. II: Clique-web inequalities
• Collapsing and lifting for the cut cone
• On the Extreme Rays of the Metric Cone
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• On the cut polytope
• Some Extremal Properties of Bipartite Subgraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item