Fast approximation schemes for Euclidean multi-connectivity problems
We present new polynomial-time approximation schemes (PTAS) for several basic minimum-cost multi-connectivity problems in geometrical graphs. We focus on low connectivity requirements. Each of our schemes either signifi- cantly improves the previously known upper time-bound or is the first PTAS for the considered problem. We provide a randomized approximation scheme for finding a biconnected graph
