Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
477867 | European Journal of Operational Research | 2006 | 10 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Sacha C. Varone,