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.
|State||Published - 2011|
|Event||23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada|
Duration: 10 Aug 2011 → 12 Aug 2011
|Conference||23rd Annual Canadian Conference on Computational Geometry, CCCG 2011|
|Period||10/08/11 → 12/08/11|