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

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

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