On the approximation of the minimum maximum stretch tree problem
Philipp E. Boksberger, Fabian Kühn, Roger P. Wattenhofer · Repository for Publications and Research Data (ETH Zurich) · 2003
Spanning trees have always been of great interest in various areas of com puter science. The same is true for the idea of shortest paths in a graph. Minimum Stretch Spanning Trees can be described as a combination of these two concepts. On the one hand they are spanning trees, on the other hand they have a minimum stretch which means that the distances between the nodes in the spanning tree remain as short as possible. We can talk about detours between endpoints of edges, which are introduced by removing these edges from the original graph in order to obtain a Minimum Stretch Spanning Tree. A spanning tree with a minimum stretch is one where the largest of these detours is minimal. Computing a Minimum Stretch Spanning Tree is known to be NP-hard for general graphs. This leads us to two simplifications of the problem. First, we restrict the input graphs to special graph families such as grids, grid subgraphs and unit disk graphs. Second, our main interest is in an approximation of the problem and not in the optimal solution. We present an algorithm that computes a spanning tree with stretch O(OP T4) in time O(n log n). Besides this we show a greedy and an evolutionary al gorithm and prove that they do not produce a spanning tree with stretch better than O(n). At last we present two algorithms for which, in the worst example found, the resulting spanning trees have stretch Ω(OP T2) but it remains open how good the approximation factors of these algorithms are.