On minimum spanning tree-like metric spaces

Abstract: We attempt to shed new light on the notion of 'tree-like' metric spaces by focusing on an approach that does not use the four-point condition. Our key question is: Given metric space

M

on

n

points, when does a fully labelled positive-weighted tree

T

exist on the same

n

vertices that precisely realises

M

using its shortest path metric? We prove that if a spanning tree representation,

T

, of

M

exists, then it is isomorphic to the unique minimum spanning tree in the weighted complete graph associated with

M

, and we introduce a fourth-point condition that is necessary and sufficient to ensure the existence of

T

whenever each distance in

M

is unique. In other words, a finite median graph, in which each geodesic distance is distinct, is simply a tree. Provided that the tie-breaking assumption holds, the fourth-point condition serves as a criterion for measuring the goodness-of-fit of the minimum spanning tree to

M

, i.e., the spanning tree-likeness of

M

. It is also possible to evaluate the spanning path-likeness of

M

. These quantities can be measured in

O (n^{4})

and

O (n^{3})

time, respectively.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: On minimum spanning tree-like metric spaces

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