Popis: |
We present a $\frac{10}{7}$-approximation algorithm for the minimum 2-vertex-connected spanning subgraph problem. Similarly to the work of Cheriyan, Sebo, and Szigeti for 2-edge-connected spanning subgraphs, our algorithm is based on computing a carefully designed ear-decomposition. |