A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems

DOI10.1016/0925-7721(93)90021-WzbMath0792.68056OpenAlexW2064509437MaRDI QIDQ1803268

David Avis, Viatcheslav Grishukhin

Publication date: 29 June 1993

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(93)90021-w

zbMATH Keywords

NP-hardDelaunay polytopesfacets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Metric extensions and the \(L^ 1\) hierarchy, Application of cut polyhedra. I, Applications of cut polyhedra. II, Complexity results for the gap inequalities for the max-cut problem, Semidefinite programming and combinatorial optimization, Non-rigidity degree of a lattice and rigid lattices, Membership testing for Bernoulli and tail-dependence matrices

Cites Work

• The classification of finite connected hypermetric spaces
• The hypermetric cone is polyhedral
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Unnamed Item
• Unnamed Item