Approximating the geometric minimum-diameter spanning tree. Conference Paper uri icon

abstract

  • Abstract Given a set P of points in the plane, a geometric minimum-diameter spanning tree (GMDST) of P is a spanning tree of P such that the longest path through the tree is minimized. In this paper, we present an approximation algorithm that generates a tree whose diameter is no more than (1+ ϵ) times that of a GMDST, for any ϵ> 0. Our algorithm reduces the problem to several grid-aligned versions of the problem and runs within time O (ϵ− 3+ n) and space O (n) improving the result by Gudmundsson et al.[4].

publication date

  • January 1, 2003

presented at event