Quasi-semi-metrics, oriented multi-cuts and related polyhedra
type: Item
instance of: scholarly article
title: Quasi-semi-metrics, oriented multi-cuts and related polyhedra
zbMATH Open document ID: 0966.52010
published in: European Journal of Combinatorics
publication date: 2001-08-06T00:00:00Z
review text: The notion of quasi-metric \(d\) on a set \(X\) generalizes that of metric on \(X\) by dropping the symmetry condition \(d(x, y) = d(y, x)\) \(\forall x, y \in X\). A quasi-metric on \(\{ 1, 2, \dots , n \}\) can be regarded as a vector \((d_{i, j})_{i \neq j}\in \mathbb{R}^{n(n-1)}\) defined by \(d_{i, j} = d(i, j)\) and thus one can consider the cone and the polytope of all quasi-metrics on \(\{1,2,\dots , n \}\). An oriented multi-cut is a quasi-metric on \(\{ 1, 2, \dots , n \}\) associated with a partition \((S_1, S_2, \dots , S_q)\), \(q \geq 2\), of this set. It is defined by \(d(S_1, S_2, \dots , S_q)(a, b) = 1\) if \(a \in S_r\), \(b \in S_t\) and \(r < t\), and otherwise \(d(S_1, S_2, \dots , S_q)(a, b) = 0\). In this paper, the authors consider the cone and the polytope respectively of all quasi-metrics and of all multi-cuts on \(\{ 1, 2, \dots , n \}\), studying in detail the cases \(n =3, 4, 5\) and formulating several conjectures for general \(n\).
reviewed by: Maria do Rosário Pinto
Mathematics Subject Classification ID: 52B11
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1513387
zbMATH Keywords: polytope
zbMATH Keywords: partition
zbMATH Keywords: graph
zbMATH Keywords: quasi-metrics
zbMATH Keywords: multi-cuts
author: Michel Deza
author: Elena Deza
describes a project that uses: PORTA
describes a project that uses: cdd
MaRDI profile type: Publication
OpenAlex ID: W2060789147
cites work: Small min-cut polyhedra
cites work: Q5610277
cites work: Directed distance in digraphs: Centers and medians
cites work: Combinatorial optimization and small polytopes
cites work: Q4309968
cites work: Q3974968
cites work: Geometry of cuts and metrics
cites work: Computing extreme rays of the metric cone for seven points
cites work: Graphic vertices of the metric polytope
cites work: The geometry of graphs and some of its algorithmic applications
cites work: Q3126163
cites work: On quasi-metric spaces
cites work: On Quasi-Metric Spaces
DOI: 10.1006/EUJC.1999.0383
Recommended article: Q4556047
Recommended article: Generalized cut and metric polytopes of graphs and simplicial complexes
Recommended article: Q3619948
Recommended article: Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings
Recommended article: On some recent results in the metric theory of polyhedra
Recommended article: Some results on quasipolyhedral convexity
Recommended article: A Note on Seminormality of Cut Polytopes
Recommended article: Q3819655
Recommended article: Q4526635
description: scientific article; zbMATH DE number 1513387