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 (8)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: The cut cone. III: On the role of triangle facets