Kantorovich distance on a weighted graph

Luigi Montrucchio, Giovanni Pistone

Published 2019-05-18Version 1

The computation of the Kantorovich distance (1-Wasserstein distance) on a finite state space may be a computationally hard problem in the case of a general distance. In this paper, we derive a simple closed form in the case of the geodesic distance on a weighted tree. Moreover, when the ground distance is defined by a graph, we show that the Kantorovich distance is the minimum of the distances on the spanning trees.