Spanning Trees and Shortest Paths in Monge Graphs

摘要

We investigate three problems on Monge graphs, i.e. complete, undirected weighted graphs whose distance matrix is a Monge matrix: (A) the minimum spanning tree problem, (B) the problem of computing all-pairs shortest paths and (C) the problem of determining a minimum weighted 1-to-all shortest path tree. For all three problems best possible algorithms (in terms of complexity) are presented.