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

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

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

This page was built for publication: A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems