This article is cited in 22 papers

A formula for the weight of a minimal filling of a finite metric space

A. Yu. Eremin<sup>ab

a</sup> M. V. Lomonosov Moscow State University
^b Delone Laboratory of Discrete and Computational Geometry, P. G. Demidov Yaroslavl State University

Abstract: We consider the problem of finding a minimal filling for a finite metric space, that is, a weighted graph of minimal weight joining a given finite metric space. We obtain a minimax formula for the weight of the minimal filling, which we use to prove various properties of minimal fillings.
Bibliography: 10 titles.

Keywords: minimal filling, finite metric spaces, graph, Gromov's problem, perimeter of a metric space.

UDC: 515.124.4+519.176

MSC: Primary 05C35; Secondary 05C05, 05C22, 51K05

Received: 21.12.2010 and 07.05.2013

DOI: 10.4213/sm7835

 English version: Sbornik: Mathematics, 2013, 204:9, 1285–1306

Bibliographic databases:

• 
• 
• 
• 
• 
• 
•