eng
Varone, Sacha
A constructive algorithm for realizing a distance matrix
http://doc.rero.ch/record/12739/files/Varone_constructive.pdf
The natural metric of a weighted graph is the length of the shortest paths between all pairs of vertices. The investigated problem consists in a representation of a given metric by a graph, such that the total length of the graph is minimized. For that purpose, we give a constructive algorithm based on a technique of reduction, fusion and deletion. We then show some results on a set of various distance matrices whose optimal realization is known.
2009-10-13T14:12:27Z
http://doc.rero.ch/record/12739