Linear-time approximation schemes for planar minimum three-edge connected and three-vertex connected spanning subgraphs

Baigong Zheng

We present the first polynomial-time approximation schemes, i.e., (1 + ε)-approximation algorithm for any constant ε > 0, for the minimum three-edge connected spanning subgraph pro…