SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES

Abstract

Given a set S of points in the plane, a geometric network for S is a graph G with vertex set S and straight edges. We consider a broadcasting situation, where one point r is an element of S is a designated source. Given a dilation factor delta, we ask for a geometric network G such that for every point v is an element of S there is a path from r to v in G of length at most delta vertical bar rv vertical bar, and such that the total edge length is minimized. We show that finding such a network of minimum total edge length is NP-hard, and give an approximation algorithm.