Finite metrics in switching classes

DOI10.1016/J.DAM.2006.04.041MaRDI QIDQ858301zbMATH OpenOpenAlexFDO

Authors Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Publication date 9 January 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.04.041

zbMATH Keywords

finite metric spaceManhattan metricsemimetricswitching classtriangle inequality

Mathematics Subject Classification ID

Graph theory (05C99) Semimetric spaces (54E25) Metric spaces, metrizability (54E35)

Review text

Let \(D\) be a finite set, \(\sigma: D\to{\mathbb R}\) any function, and \(g:D\times D\to {\mathbb R}\) a function satisfying the conditions \(g(x,x)=0\) and \(g(x,y)=g(y,x)\). The authors introduce the function \(g^\sigma\) by the equalities \(g^\sigma(x,x)=0\) and \(g^\sigma(x,y)=\sigma(x)+g(x,y)+\sigma(y)\) if \(x\neq y\). The authors fix \(g\) and consider the set of all possible \(g^\sigma\), denoted by \([g]\). The paper is devoted to the structure of subsets of \([g]\) consisting of metrics, semimetrics, and \(L^1\)-embeddable semimetrics (cut semimetrics).

Recommendations

• Natural metrics and their properties. I: Submetrics and overmetrics
• Main metric invariants of finite metric spaces
• Generalizations of finite metrics and cuts
• On a duality between metrics and \(\Sigma\)-proximities
• Main metric invariants of finite metric spaces. III

Cites work

• Dynamic labeled 2-structures
• Geometry of cuts and metrics
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 3745240 (Why is no real title available?)
• scientific article; zbMATH DE number 3774306 (Why is no real title available?)
• scientific article; zbMATH DE number 3547309 (Why is no real title available?)
• scientific article; zbMATH DE number 1478125 (Why is no real title available?)
• scientific article; zbMATH DE number 1789916 (Why is no real title available?)
• scientific article; zbMATH DE number 3225111 (Why is no real title available?)
• Metrics and undirected cuts
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms

Cited in

(2)

• Functions transferring metrics to metrics
• Natural metrics and their properties. I: Submetrics and overmetrics

This page was built for publication: Finite metrics in switching classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q858301)