Connecting two trees with optimal routing cost

Mong-Jen Kao, Bastian Katz, Marcus Krug, D. T. Lee, Martin Nöllenburg, Ignaz Rutter, Dorothea Wagner

Research output: Contribution to conferencePaperpeer-review


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.

Original languageEnglish
Number of pages5
StatePublished - 10 Aug 2011
Event23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada
Duration: 10 Aug 201112 Aug 2011


Conference23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
CityToronto, ON


Dive into the research topics of 'Connecting two trees with optimal routing cost'. Together they form a unique fingerprint.

Cite this