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

    Abstract

    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
    StatePublished - 2011
    Event23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada
    Duration: 10 Aug 201112 Aug 2011

    Conference

    Conference23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
    Country/TerritoryCanada
    CityToronto, ON
    Period10/08/1112/08/11

    Fingerprint

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

    Cite this