A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems
type: Item
instance of: scholarly article
title: A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems
zbMATH Open document ID: 0792.68056
DOI: 10.1016/0925-7721(93)90021-W
published in: Computational Geometry
publication date: 1993-06-29T00:00:00Z
review text: After a short introduction the authors give a complete description of \(L\)-polytopes (or Delaunay polytopes) related to facets. Upper bounds on the \(k\)-gonality of facet defining inequalities and on the number of facets of the hypermetric cone are studied. In the last chapter applications to computational complexity are discussed. The problem determining hypermetricity lies in co-NP. The authors give other related problems which are in co-NP (testing minimality of a lattice vector, \((2m+1)\)-gonality testing) and NP-hard (strong hypermetricity, (largest) complete bipartite subgraph).
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 220605
zbMATH Keywords: Delaunay polytopes
zbMATH Keywords: facets
zbMATH Keywords: NP-hard
author: David Avis
author: Viacheslav Grishukhin
reviewed by: Hans-Dietrich Hecker
MaRDI profile type: Publication
cites work: The cut cone,L1 embeddability, complexity, and multicommodity flows
cites work: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
cites work: The hypermetric cone is polyhedral
cites work: Q3137180
cites work: The classification of finite connected hypermetric spaces
cites work: Q4198056
full work available at URL: 0925-7721(93)90021-w
OpenAlex ID: W2064509437
description: scientific article; zbMATH DE number 220605