Graphic vertices of the metric polytope

DOI10.1016/0012-365X(94)00091-VzbMath0854.05095MaRDI QIDQ1916387

Monique Laurent

Publication date: 3 July 1996

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

polytopeswitching classgraphic vertices

Mathematics Subject Classification ID

Trees (05C05) Graph theory (05C99)

Related Items (11)

Application of cut polyhedra. I ⋮ Robinsonian matrices: recognition challenges ⋮ One-third-integrality in the max-cut problem ⋮ Partial Lasserre relaxation for sparse Max-Cut ⋮ On the generation of metric TSP instances with a large integrality gap by branch-and-cut ⋮ Cubic graphs, their Ehrhart quasi-polynomials, and a scissors congruence phenomenon ⋮ Triameter of graphs ⋮ A counterexample to the dominating set conjecture ⋮ Computing extreme rays of the metric cone for seven points ⋮ The isometries of the cut, metric and hypermetric cones ⋮ Quasi-semi-metrics, oriented multi-cuts and related polyhedra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On cuts and matchings in planar graphs
• Combinatorial approaches to multiflow problems
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Weakly bipartite graphs and the max-cut problem
• Computing extreme rays of the metric cone for seven points
• One-third-integrality in the max-cut problem
• On the Extreme Rays of the Metric Cone
• Extremal Metrics Induced by Graphs
• Information Bounds Are Weak in the Shortest Distance Problem
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• On the cut polytope
• The cut cone. III: On the role of triangle facets

This page was built for publication: Graphic vertices of the metric polytope