Minimum spanning trees and types of dissimilarities
type: Item
instance of: scholarly article
title: Minimum spanning trees and types of dissimilarities
zbMATH Open document ID: 0848.05022
author: Bruno Leclerc
published in: European Journal of Combinatorics
publication date: 1996-07-03T00:00:00Z
review text: The author surveys and brings together a set of observations concerning dissimilarities, i.e., functions \(d\): \(X^2 \to [0, \infty)\) such that \(d(x,x) = 0\) and such that \(d(x,y) = d(y,x)\), and dissimilarity preorders \(R\) (reflexive and transitive relations) on \(X^2\), \(X\) a finite set, with the emphasis on compatibility relationships which may exist between dissimilarity and dissimilarity preorders. In particular, ultrametric and tree dissimilarities are of greatest interest as the penultimate and ultimate types on a ladder conditioned by adding one extra hypothesis at each step. Once this is done a sequence of equivalencies in the form of classification theorems is established and from these theorems corollaries extract simpler but relevant information. Proofs even of known results are thus sometimes novel and often improved as well. The theoretical points emphasize the association of particular spanning trees of \(X\) with particular dissimilarity preorders \(R\) in such a way as to be most compatible and best in the natural order on dissimilarities provided by pointwise comparison on \(X^2\). Results in Data Analysis and Operations Research point to the great utility of these notions. Furthermore, the range of papers noted in the references provide useful leads to non-francophones that could easily be missed but for articles such as these, including several by this author.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 90B99
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 871019
zbMATH Keywords: dissimilarity
zbMATH Keywords: dissimilarity preorders
zbMATH Keywords: tree
zbMATH Keywords: spanning trees
reviewed by: J. Neggers
MaRDI profile type: Publication
full work available at URL: eujc.1996.0021
OpenAlex ID: W2006908708
DOI: 10.1006/EUJC.1996.0021
description: scientific article; zbMATH DE number 871019