Connecting two trees with optimal routing cost

We study the problem of finding the optimal connection between two disconnected vertex-weighted trees. We are given a distance function on the vertices and seek to minimize the routing cost of the tree resulting from adding one single edge between the two trees. The routing cost is defined as the sum of the weighted distances between all pairs of vertices in the induced tree-metric. The problem arises when augmenting and/or repairing communication networks or infrastructure networks. We present an asymptotically optimal quadratic-time algorithm for the general case and show that the problem can be solved more efficiently for the Euclidean metric, when vertices are mapped to points in the plane, as well as for compactly representable graph metrics.