Approximation Schemes for Minimum-Cost k-Connectivity Problems in Geometric Graphs
Teofilo F. Gonzalez · 2007
We survey the recent progress in the design of approximation schemes for geometric variants of the following classical optimization problem: for a given undirected weighted graph, find its minimum-cost subgraph that satisfies a priori given multiconnectivity requirements. We present the approximation schemes for various geometric minimum-cost k-connectivity problems and for geometric survivability problems, giving a detailed tutorial of the novel techniques developed for these algorithms. We also shortly discuss extensions to include planar graphs.